\uc548\ub155\ud558\uc138\uc694! \uc774\ubc88 \uae00\uc5d0\uc11c\ub294 \uc790\ubc14\ub97c \uc0ac\uc6a9\ud55c \ucf54\ub529\ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc720\uc6a9\ud558\uac8c \uc4f0\uc77c \uc218 \uc788\ub294 \uc54c\uace0\ub9ac\uc998 \uc911 \ud558\ub098\uc778 \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac<\/strong>\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub294 \uc8fc\ub85c \uad6c\uac04 \ucffc\ub9ac\uc640 \uad6c\uac04 \uc5c5\ub370\uc774\ud2b8\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \ucc98\ub9ac\ud558\uae30 \uc704\ud574 \uc0ac\uc6a9\ub429\ub2c8\ub2e4. \uc774 \uae00\uc5d0\uc11c\ub294 \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\uc758 \uae30\ubcf8 \uac1c\ub150\uacfc \uc774\uc5d0 \ub300\ud55c \uc608\uc81c \ubb38\uc81c, \uadf8\ub9ac\uace0 \uadf8 \ubb38\uc81c\uc758 \ud574\uacb0 \uacfc\uc815\uc744 \uc790\uc138\ud788 \uc124\uba85\ub4dc\ub9ac\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub294 \ubc30\uc5f4\uc5d0\uc11c \ud2b9\uc815 \uad6c\uac04\uc758 \uc815\ubcf4\ub97c \uc800\uc7a5\ud558\uace0 \ucffc\ub9ac\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \ucc98\ub9ac\ud558\uae30 \uc704\ud55c \ub370\uc774\ud130 \uad6c\uc870\uc785\ub2c8\ub2e4. \uc8fc\ub85c \ub2e4\uc74c\uacfc \uac19\uc740 \uc791\uc5c5\uc744 \uc9c0\uc6d0\ud569\ub2c8\ub2e4:<\/p>\n \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub294 O(log n) \uc2dc\uac04\uc5d0 \ucffc\ub9ac\ub97c \ucc98\ub9ac\ud560 \uc218 \uc788\uc73c\uba70, \uacf5\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(n)\uc785\ub2c8\ub2e4. \uc774\ub97c \ud1b5\ud574 \ub300\uaddc\ubaa8\uc758 \ub370\uc774\ud130\ub97c \ud6a8\uacfc\uc801\uc73c\ub85c \ub2e4\ub8f0 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n \uc774\uc81c ‘\uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac’\ub97c \ud65c\uc6a9\ud55c \ubb38\uc81c\ub97c \ud558\ub098 \ud480\uc5b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \uc8fc\uc5b4\uc9c4 \uc815\uc218 \ubc30\uc5f4\uc774 \uc788\uc744 \ub54c, \ud2b9\uc815 \uad6c\uac04\uc758 \ud569\uc744 \uad6c\ud558\uace0, \ud2b9\uc815 \uc778\ub371\uc2a4\uc5d0 \uc788\ub294 \uac12\uc744 \uc5c5\ub370\uc774\ud2b8 \ud558\ub294 \ub450 \uac00\uc9c0 \uae30\ub2a5\uc744 \uc81c\uacf5\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc138\uc694.<\/p>\n \uad6c\ud604\ud574\uc57c \ud558\ub294 \uae30\ub2a5\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n \uba3c\uc800 \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub97c \uad6c\ud604\ud574\uc57c \ud569\ub2c8\ub2e4. \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub294 \ube44\uc0c1\uc704 \ub178\ub4dc\ub85c\ubd80\ud130 \ub9ac\ud504 \ub178\ub4dc\uae4c\uc9c0\uc758 \ud569\uc744 \uc800\uc7a5\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c \uad6c\uc131\ub429\ub2c8\ub2e4. \uc774\ub97c \uc704\ud55c \ubc30\uc5f4 \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac \ud074\ub798\uc2a4\ub97c \ud3ec\ud568\ud558\uc5ec \uc785\ub825\uc744 \ubc1b\uc544 \ucffc\ub9ac\ub97c \ucc98\ub9ac\ud558\ub294 \uba54\uc778 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n\uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub780?<\/h2>\n
\n
\ubb38\uc81c \uc18c\uac1c<\/h2>\n
\ubb38\uc81c \uc124\uba85<\/h3>\n
\n
l<\/code>\uacfc r<\/code>\uac00 \uc8fc\uc5b4\uc9c0\uba74, l<\/code>\uacfc r<\/code> \uc0ac\uc774\uc758 \ud569\uc744 \ubc18\ud658\ud569\ub2c8\ub2e4.<\/li>\nindex<\/code>\uc758 \uac12\uc744 value<\/code>\ub85c \uc5c5\ub370\uc774\ud2b8 \ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n\uc785\ub825 \ud615\uc2dd<\/h3>\n
\n\uccab \ubc88\uc9f8 \uc904: \ubc30\uc5f4\uc758 \ud06c\uae30 n (1 \u2264 n \u2264 10^5)\n\ub450 \ubc88\uc9f8 \uc904: n\uac1c\uc758 \uc815\uc218 (1 \u2264 arr[i] \u2264 10^9)\n\uc138 \ubc88\uc9f8 \uc904: \ucffc\ub9ac\uc758 \uc218 q\n\ub2e4\uc74c q\uc904: \ucffc\ub9ac\ub294 \ub450 \uac00\uc9c0 \ud615\uc2dd \uc911 \ud558\ub098\uc785\ub2c8\ub2e4:\n 1. 1 l r (\uad6c\uac04 \ud569 \ucffc\ub9ac)\n 2. 2 index value (\uc5c5\ub370\uc774\ud2b8 \ucffc\ub9ac)\n<\/pre>\n
\ucd9c\ub825 \ud615\uc2dd<\/h3>\n
\n\uad6c\uac04 \ud569 \ucffc\ub9ac\uc5d0 \ub300\ud55c \uacb0\uacfc\ub97c \ud55c \uc904\uc529 \ucd9c\ub825\ud569\ub2c8\ub2e4.\n<\/pre>\n
\ubb38\uc81c \ud574\uacb0 \uacfc\uc815<\/h2>\n
1. \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac \uad6c\ud604<\/h3>\n
tree<\/code>\ub97c \uc120\uc5b8\ud558\uace0, \ud2b8\ub9ac\ub97c \uad6c\ucd95\ud558\ub294 \uba54\uc18c\ub4dc\ub97c \uc791\uc131\ud558\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\njava\npublic class SegmentTree {\n private int[] tree;\n private int n;\n\n public SegmentTree(int[] arr) {\n n = arr.length;\n tree = new int[n * 4];\n buildTree(arr, 0, 0, n - 1);\n }\n\n private void buildTree(int[] arr, int node, int start, int end) {\n if (start == end) {\n tree[node] = arr[start];\n } else {\n int mid = (start + end) \/ 2;\n buildTree(arr, node * 2 + 1, start, mid);\n buildTree(arr, node * 2 + 2, mid + 1, end);\n tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];\n }\n }\n\n \/\/ \uad6c\uac04 \ud569 \ucffc\ub9ac \uba54\uc18c\ub4dc\n public int rangeSum(int l, int r) {\n return rangeSumHelper(0, 0, n - 1, l, r);\n }\n\n private int rangeSumHelper(int node, int start, int end, int l, int r) {\n if (r < start || end < l) {\n return 0; \/\/ \ucffc\ub9ac \ubc94\uc704\uac00 \ub178\ub4dc \ubc94\uc704\uc640 \uacb9\uce58\uc9c0 \uc54a\uc74c\n }\n if (l <= start && end <= r) {\n return tree[node]; \/\/ \ub178\ub4dc \ubc94\uc704\uac00 \ucffc\ub9ac \ubc94\uc704\uc5d0 \ud3ec\ud568\ub428\n }\n int mid = (start + end) \/ 2;\n int leftSum = rangeSumHelper(node * 2 + 1, start, mid, l, r);\n int rightSum = rangeSumHelper(node * 2 + 2, mid + 1, end, l, r);\n return leftSum + rightSum;\n }\n\n \/\/ \uc5c5\ub370\uc774\ud2b8 \uba54\uc18c\ub4dc\n public void update(int index, int value) {\n updateHelper(0, 0, n - 1, index, value);\n }\n\n private void updateHelper(int node, int start, int end, int index, int value) {\n if (start == end) {\n tree[node] = value;\n } else {\n int mid = (start + end) \/ 2;\n if (start <= index && index <= mid) {\n updateHelper(node * 2 + 1, start, mid, index, value);\n } else {\n updateHelper(node * 2 + 2, mid + 1, end, index, value);\n }\n tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];\n }\n }\n}\n<\/code><\/pre>\n2. \uba54\uc778 \ud504\ub85c\uadf8\ub7a8<\/h3>\n
java\nimport java.util.Scanner;\n\npublic class Main {\n public static void main(String[] args) {\n Scanner scanner = new Scanner(System.in);\n \n int n = scanner.nextInt();\n int[] arr = new int[n];\n \n for (int i = 0; i < n; i++) {\n arr[i] = scanner.nextInt();\n }\n\n SegmentTree segmentTree = new SegmentTree(arr);\n \n int q = scanner.nextInt();\n for (int i = 0; i < q; i++) {\n int type = scanner.nextInt();\n if (type == 1) { \/\/ \uad6c\uac04 \ud569 \ucffc\ub9ac\n int l = scanner.nextInt();\n int r = scanner.nextInt();\n System.out.println(segmentTree.rangeSum(l, r)); \n } else if (type == 2) { \/\/ \uc5c5\ub370\uc774\ud2b8 \ucffc\ub9ac\n int index = scanner.nextInt();\n int value = scanner.nextInt();\n segmentTree.update(index, value);\n }\n }\n \n scanner.close();\n }\n}\n<\/code><\/pre>\n3. \uc2dc\uac04 \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n