\n \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac(Segment Tree)\ub294 \ubc30\uc5f4\uc758 \uad6c\uac04 \ud569, \uad6c\uac04 \ucd5c\uc18c\uac12, \uad6c\uac04 \ucd5c\ub300\uac12 \ub4f1\uc744 \ud6a8\uacfc\uc801\uc73c\ub85c \uad6c\ud560 \uc218 \uc788\ub294 \uc790\ub8cc\uad6c\uc870\uc785\ub2c8\ub2e4. \uc774 \uc790\ub8cc\uad6c\uc870\ub294 \ud2b9\ud788 \uad6c\uac04 \ucffc\ub9ac\uc640 \uc5c5\ub370\uc774\ud2b8\uac00 \ube48\ubc88\ud558\uac8c \uc774\ub8e8\uc5b4\uc9c0\ub294 \uc0c1\ud669\uc5d0\uc11c \ube60\ub978 \uc131\ub2a5\uc744 \ubc1c\ud718\ud569\ub2c8\ub2e4. \uc774 \uac15\uc88c\uc5d0\uc11c\ub294 \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\uc758 \uae30\ubcf8\uc801\uc778 \uad6c\uc870\uc640 \uad6c\ud604 \ubc29\ubc95, \uadf8\ub9ac\uace0 \uc2e4\uc81c \ucf54\ub529\ud14c\uc2a4\ud2b8\uc5d0\uc11c \ud65c\uc6a9\ud560 \uc218 \uc788\ub294 \ubb38\uc81c\ub97c \ub2e4\ub8e8\uaca0\uc2b5\ub2c8\ub2e4.\n<\/p>\n
\n \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub294 \ubc30\uc5f4\uc758 \ud2b9\uc815 \uad6c\uac04\uc5d0 \ub300\ud55c \uc815\ubcf4\ub97c \uc800\uc7a5\ud558\uae30 \uc704\ud55c \uc774\uc9c4 \ud2b8\ub9ac \ud615\ud0dc\uc758 \uc790\ub8cc\uad6c\uc870\uc785\ub2c8\ub2e4. \uac01 \ub178\ub4dc\ub294 \ud2b9\uc815 \uad6c\uac04\uc758 \uc815\ubcf4\ub97c \uc800\uc7a5\ud558\uace0, \uc774\ub97c \ud1b5\ud574 \ube60\ub978 \ucffc\ub9ac\uc640 \uc5c5\ub370\uc774\ud2b8\uac00 \uac00\ub2a5\ud569\ub2c8\ub2e4. \uc8fc\ub85c \ub2e4\uc74c\uacfc \uac19\uc740 \ub450 \uac00\uc9c0 \uc791\uc5c5\uc744 \ud6a8\uc728\uc801\uc73c\ub85c \uc218\ud589\ud558\ub294 \ub370 \uc0ac\uc6a9\ub429\ub2c8\ub2e4.\n<\/p>\n
\n \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub294 \uc644\uc804 \uc774\uc9c4 \ud2b8\ub9ac\ub85c \uad6c\uc131\ub418\uba70, \uc77c\ubc18\uc801\uc73c\ub85c \ub2e4\uc74c\uacfc \uac19\uc740 \ubc29\uc2dd\uc73c\ub85c \ubc30\uc5f4\uc744 \uad6c\uc131\ud569\ub2c8\ub2e4. \uc774\ub97c \uc704\ud574, \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\uc758 \uac01 \ub178\ub4dc\ub294 \ubd80\ubaa8\uc640 \uc790\uc2dd \uac04\uc758 \uad00\uacc4\ub97c \ud1b5\ud574 \uc815\uc758\ub429\ub2c8\ub2e4. \ubc30\uc5f4\uc758 \ub178\ub4dc\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \uaddc\uce59\uc744 \ub530\ub985\ub2c8\ub2e4:\n<\/p>\n
i<\/code>\uc758 \uc67c\ucabd \uc790\uc2dd\uc774 2*i<\/code>, \uc624\ub978\ucabd \uc790\uc2dd\uc774 2*i + 1<\/code><\/li>\n- \ub9ac\ud504 \ub178\ub4dc\ub294 \uc8fc\uc5b4\uc9c4 \ubc30\uc5f4\uc758 \uac01 \uc6d0\uc18c\uc640 \uc0c1\ub300\ud558\ub294 \uc778\ub371\uc2a4\uc5d0 \uc800\uc7a5\ub429\ub2c8\ub2e4.<\/li>\n<\/ul>\n
\uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac \uad6c\ud604<\/h2>\n
\n \ucf54\ud2c0\ub9b0\uc744 \uc774\uc6a9\ud55c \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\uc758 \uad6c\ud604\uc744 \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uba3c\uc800, \uae30\ubcf8\uc801\uc778 \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac \ud074\ub798\uc2a4\ub97c \uc815\uc758\ud558\uace0, \ucd08\uae30\ud654, \uc5c5\ub370\uc774\ud2b8 \ubc0f \ucffc\ub9ac \uae30\ub2a5\uc744 \uad6c\ud604\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n<\/p>\n
1. \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac \ud074\ub798\uc2a4 \uc815\uc758<\/h3>\n\nclass SegmentTree(private val array: IntArray) {\n private val size: Int = array.size\n private val tree: IntArray = IntArray(4 * size)\n \n init {\n build(0, 0, size - 1)\n }\n\n private fun build(node: Int, start: Int, end: Int) {\n if (start == end) {\n tree[node] = array[start]\n } else {\n val mid = (start + end) \/ 2\n build(2 * node + 1, start, mid)\n build(2 * node + 2, mid + 1, end)\n tree[node] = tree[2 * node + 1] + tree[2 * node + 2]\n }\n }\n\n fun update(index: Int, value: Int) {\n update(0, 0, size - 1, index, value)\n }\n\n private fun update(node: Int, start: Int, end: Int, index: Int, value: Int) {\n if (start == end) {\n array[index] = value\n tree[node] = value\n } else {\n val mid = (start + end) \/ 2\n if (index in start..mid) {\n update(2 * node + 1, start, mid, index, value)\n } else {\n update(2 * node + 2, mid + 1, end, index, value)\n }\n tree[node] = tree[2 * node + 1] + tree[2 * node + 2]\n }\n }\n \n fun query(L: Int, R: Int): Int {\n return query(0, 0, size - 1, L, R)\n }\n\n private fun query(node: Int, start: Int, end: Int, L: Int, R: Int): Int {\n if (R < start || end < L) return 0 \/\/ \ucffc\ub9ac \ubc94\uc704\uc640 \ub178\ub4dc \ubc94\uc704\uac00 \uacb9\uce58\uc9c0 \uc54a\uc74c\n if (L <= start && end <= R) return tree[node] \/\/ \ub178\ub4dc \ubc94\uc704\uac00 \ucffc\ub9ac \ubc94\uc704\uc5d0 \ud3ec\ud568\ub428\n val mid = (start + end) \/ 2\n val leftSum = query(2 * node + 1, start, mid, L, R)\n val rightSum = query(2 * node + 2, mid + 1, end, L, R)\n return leftSum + rightSum\n }\n}\n<\/code><\/pre>\n2. \uc0ac\uc6a9 \uc608\uc2dc<\/h3>\n
\n \uc704\uc5d0\uc11c \uc815\uc758\ud55c \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub97c \uc0ac\uc6a9\ud558\uc5ec \uad6c\uac04\uc758 \ud569\uc744 \uad6c\ud558\uace0 \uc5c5\ub370\uc774\ud2b8\ub97c \uc218\ud589\ud558\ub294 \uc608\uc2dc\ub97c \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n<\/p>\n
\nfun main() {\n val array = intArrayOf(1, 3, 5, 7, 9, 11)\n val segmentTree = SegmentTree(array)\n\n println(\"\uad6c\uac04 [1, 3]\uc758 \ud569: ${segmentTree.query(1, 3)}\") \/\/ 3 + 5 + 7 = 15\n segmentTree.update(1, 10) \/\/ array[1]\ub97c 10\uc73c\ub85c \uc5c5\ub370\uc774\ud2b8\n println(\"\uc5c5\ub370\uc774\ud2b8 \ud6c4 \uad6c\uac04 [1, 3]\uc758 \ud569: ${segmentTree.query(1, 3)}\") \/\/ 10 + 5 + 7 = 22\n}\n<\/code><\/pre>\n\ucf54\ub529\ud14c\uc2a4\ud2b8 \ubb38\uc81c<\/h2>\n
\n \uc774\uc81c \uc2e4\uc81c \ucf54\ub529\ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ub2e4\ub904\uc9c0\ub294 \ubb38\uc81c\ub97c \ud568\uaed8 \ud480\uc5b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc544\ub798 \ubb38\uc81c\ub294 \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub97c \ud65c\uc6a9\ud55c \uc751\uc6a9 \ubb38\uc81c\uc785\ub2c8\ub2e4.\n<\/p>\n
\ubb38\uc81c: \uad6c\uac04 \ud569\uacfc \uc5c5\ub370\uc774\ud2b8<\/h3>\n
\n \uc8fc\uc5b4\uc9c4 \ubc30\uc5f4\uc758 \ud2b9\uc815 \uad6c\uac04\uc5d0 \ub300\ud55c \ud569\uc744 \uad6c\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \ucd94\uac00\ub85c \ud2b9\uc815 \uc778\ub371\uc2a4\uc758 \uac12\uc744 \uc5c5\ub370\uc774\ud2b8\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n<\/p>\n
\ubb38\uc81c \uc124\uba85<\/h4>\n\n- N\uac1c\uc758 \uc815\uc218\ub85c \uc774\ub8e8\uc5b4\uc9c4 \ubc30\uc5f4\uc774 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.\n- \uc774\uc804\uc758 \ucffc\ub9ac \uacb0\uacfc\ub85c\ubd80\ud130 Q\ubc88 \ub9cc\ud07c \ub2e4\uc74c\uc758 \uc791\uc5c5\uc744 \uc218\ud589\ud569\ub2c8\ub2e4.\n 1. \"1 L R\" \ucffc\ub9ac\ub294 \ubc30\uc5f4\uc758 \uc778\ub371\uc2a4 L\ubd80\ud130 R\uae4c\uc9c0\uc758 \ud569\uc744 \uc694\uccad\ud569\ub2c8\ub2e4.\n 2. \"2 X Y\" \ucffc\ub9ac\ub294 \uc778\ub371\uc2a4 X\uc758 \uac12\uc744 Y\ub85c \uc5c5\ub370\uc774\ud2b8\ud569\ub2c8\ub2e4.\n<\/pre>\n\uc785\ub825 \ud615\uc2dd<\/h4>\n\n- \uccab \ubc88\uc9f8 \uc904\uc5d0\ub294 \ubc30\uc5f4\uc758 \ud06c\uae30 N\uacfc \ucffc\ub9ac\uc758 \uac1c\uc218 Q\uac00 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.\n- \ub450 \ubc88\uc9f8 \uc904\uc5d0\ub294 N\uac1c\uc758 \uc815\uc218\uac00 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.\n- \uadf8 \ub2e4\uc74c Q\uac1c\uc758 \uc904\uc5d0\ub294 \ucffc\ub9ac\uac00 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.\n<\/pre>\n\ucd9c\ub825 \ud615\uc2dd<\/h4>\n\n- \uac01 \"1 L R\" \ucffc\ub9ac\uc5d0 \ub300\ud574 \uad6c\uac04\uc758 \ud569\uc744 \ucd9c\ub825\ud569\ub2c8\ub2e4.\n<\/pre>\n\uc785\ub825 \uc608\uc2dc<\/h4>\n\n5 3\n1 2 3 4 5\n1 1 3\n2 1 10\n1 1 3\n<\/pre>\n\ucd9c\ub825 \uc608\uc2dc<\/h4>\n\n6\n<\/pre>\n\ubb38\uc81c \ud480\uc774<\/h2>\n
\n \ud574\ub2f9 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub97c \uc0ac\uc6a9\ud558\uc5ec \ud6a8\uc728\uc801\uc73c\ub85c \uad6c\uac04 \ud569 \ucffc\ub9ac\uc640 \uc5c5\ub370\uc774\ud2b8 \uc5f0\uc0b0\uc744 \uc2e4\ud589\ud558\ub3c4\ub85d \uad6c\ud604\ud569\ub2c8\ub2e4. \uc785\ub825\uc73c\ub85c\ubd80\ud130 \ub370\uc774\ud130\ub97c \ubc1b\uace0 \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub97c \ucd08\uae30\ud654\ud55c \ud6c4 \ucffc\ub9ac\ub97c \ucc98\ub9ac\ud558\ub294 \uad6c\uc870\ub97c \uac00\uc9d1\ub2c8\ub2e4.\n<\/p>\n
\uad6c\ud604<\/h3>\n\nfun main() {\n val (n, q) = readLine()!!.split(\" \").map { it.toInt() }\n val array = readLine()!!.split(\" \").map { it.toInt() }.toIntArray()\n val segmentTree = SegmentTree(array)\n\n repeat(q) {\n val query = readLine()!!.split(\" \").map { it.toInt() }\n if (query[0] == 1) {\n \/\/ \uad6c\uac04 \ud569 \ucffc\ub9ac\n val sum = segmentTree.query(query[1] - 1, query[2] - 1)\n println(sum)\n } else if (query[0] == 2) {\n \/\/ \uc5c5\ub370\uc774\ud2b8 \ucffc\ub9ac\n segmentTree.update(query[1] - 1, query[2])\n }\n }\n}\n<\/code><\/pre>\n\uacb0\ub860<\/h2>\n
\n \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\uc758 \uae30\ubcf8 \uac1c\ub150 \ubc0f \uad6c\ud604 \ubc29\ubc95\uc744 \uc775\ud614\uc2b5\ub2c8\ub2e4. \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub294 \ud6a8\uc728\uc801\uc778 \uad6c\uac04 \ucffc\ub9ac\uc640 \uc5c5\ub370\uc774\ud2b8 \uad6c\ud604\uc5d0 \ub9e4\uc6b0 \uc720\uc6a9\ud55c \uc790\ub8cc\uad6c\uc870\uc774\uba70, \ucf54\ub529\ud14c\uc2a4\ud2b8 \ubb38\uc81c\uc5d0 \uc790\uc8fc \ucd9c\uc81c\ub429\ub2c8\ub2e4. \uc774\ubc88 \uc608\uc81c\ub97c \ud1b5\ud574 \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\uc758 \uc751\uc6a9\uc744 \uc775\ud614\uae30\ub97c \ubc14\ub77c\uba70, \uc774\ub97c \ud1b5\ud574 \ud5a5\ud6c4 \ub2e4\uc591\ud55c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ub370 \ub3c4\uc6c0\uc774 \ub418\uae38 \ubc14\ub78d\ub2c8\ub2e4.\n<\/p>\n
\n \ucf54\ub529\ud14c\uc2a4\ud2b8 \uc900\ube44 \uc2dc\uc5d0\ub294 \uc774\ub7ec\ud55c \ub2e4\uc591\ud55c \uc790\ub8cc\uad6c\uc870\uc640 \uc54c\uace0\ub9ac\uc998\uc744 \uccb4\uacc4\uc801\uc73c\ub85c \ud559\uc2b5\ud558\uc5ec \uc751\uc6a9 \ub2a5\ub825\uc744 \ud0a4\uc6b0\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4. \uc55e\uc73c\ub85c\ub3c4 \ub2e4\uc591\ud55c \uc790\ub8cc\uad6c\uc870\uc640 \uc54c\uace0\ub9ac\uc998\uc744 \ud1b5\ud574 \ub354 \ub098\uc740 \ubb38\uc81c \ud574\uacb0 \ub2a5\ub825\uc744 \uac16\ucd94\uc2dc\uae30 \ubc14\ub78d\ub2c8\ub2e4.\n<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"