\n \uc54c\uace0\ub9ac\uc998 \ub300\ud68c\ub098 \ucf54\ub529 \uc778\ud130\ubdf0\uc5d0\uc11c \ud6a8\uc728\uc801\uc73c\ub85c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c \uae30\uc220 \uc911 \ud558\ub098\uac00 \ubc14\ub85c \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac(Segment Tree)<\/strong>\uc785\ub2c8\ub2e4. \n \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub294 \ubc30\uc5f4\uc758 \uad6c\uac04\uc5d0 \ub300\ud55c \uc815\ubcf4\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \uad00\ub9ac\ud558\uae30 \uc704\ud55c \uc790\ub8cc\uad6c\uc870\uc785\ub2c8\ub2e4. \n \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub294 \uc544\ub798\uc640 \uac19\uc740 \uad6c\uc870\ub85c \uad6c\uc131\ub429\ub2c8\ub2e4:\n<\/p>\n \n \uc790 \uc774\uc81c, \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub97c \uc0ac\uc6a9\ud558\uc5ec \ud574\uacb0\ud560 \uc218 \uc788\ub294 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \uc18c\uac1c\ud569\ub2c8\ub2e4.\n<\/p>\n \n \uc8fc\uc5b4\uc9c4 \uc815\uc218 \ubc30\uc5f4\uc5d0\uc11c \ub2e4\uc74c\uc758 \ub450 \uac00\uc9c0 \uc791\uc5c5\uc744 \ud6a8\uc728\uc801\uc73c\ub85c \ucc98\ub9ac\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc138\uc694.\n<\/p>\n \n \uccab \uc904\uc5d0 \ubc30\uc5f4\uc758 \ud06c\uae30 \ucffc\ub9ac\uc758 \ud615\uc2dd\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n \n \uc774\uc81c C#\uc744 \uc0ac\uc6a9\ud558\uc5ec \uc704\uc758 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub97c \uad6c\ud604\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n<\/p>\n \n \uc704\uc758 C# \ucf54\ub4dc\ub294 \uc8fc\uc5b4\uc9c4 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\uc758 \uad6c\ud604\uc785\ub2c8\ub2e4. \n \uba54\uc778 \ud568\uc218\uc5d0\uc11c\ub294 \ubc30\uc5f4\uc758 \ud06c\uae30\uc640 \ucffc\ub9ac\uc758 \uc218\ub97c \uc785\ub825\ubc1b\uace0, \uc8fc\uc5b4\uc9c4 \ubc30\uc5f4\ub85c \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub97c \uad6c\ucd95\ud55c \ub2e4\uc74c, \ucffc\ub9ac\uc5d0 \ub530\ub77c \n \uc774\ubc88 \uae00\uc5d0\uc11c\ub294 C#\uc744 \uc774\uc6a9\ud55c \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\uc758 \uad6c\ud604\uacfc \uad6c\uac04 \ud569 \ucffc\ub9ac \ubc0f \uc5c5\ub370\uc774\ud2b8 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uc558\uc2b5\ub2c8\ub2e4. <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
\n \uc774 \uae00\uc5d0\uc11c\ub294 \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\uc758 \uae30\ubcf8 \uac1c\ub150\uacfc \ud568\uaed8 \uc2e4\uc81c \ubb38\uc81c\ub97c \ud1b5\ud574 \uadf8 \uc368\ubcf4\ub294 \ubc29\ubc95\uc744 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub294 \uc8fc\ub85c \uad6c\uac04 \ucffc\ub9ac \ubb38\uc81c\uc5d0\uc11c \ub9e4\uc6b0 \uc720\uc6a9\ud558\uac8c \uc0ac\uc6a9\ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n \ud2b9\ud788, \uad6c\uac04 \ud569, \uad6c\uac04 \ucd5c\uc18c\/\ucd5c\ub300\uac12, \uad6c\uac04 \uc5c5\ub370\uc774\ud2b8 \ub4f1\uc758 \uc791\uc5c5\uc744 \ud6a8\uc728\uc801\uc73c\ub85c \ucc98\ub9ac\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n<\/p>\n\uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub780?<\/h2>\n
\n \uc774\ub97c \ud1b5\ud574 \ud2b9\uc815 \uad6c\uac04\uc5d0 \ub300\ud55c \ucffc\ub9ac \uc5f0\uc0b0 \ubc0f \uc5c5\ub370\uc774\ud2b8\ub97c \ub85c\uadf8 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4(logarithmic time complexity)\ub85c \ucc98\ub9ac\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub294 \uc77c\ubc18\uc801\uc73c\ub85c \uc774\uc9c4 \ud2b8\ub9ac \ud615\ud0dc\ub85c \uad6c\uc131\ub418\uba70, \uac01 \ub178\ub4dc\ub294 \ud2b9\uc815 \uad6c\uac04\uc5d0 \ub300\ud55c \uc815\ubcf4\ub97c \uc800\uc7a5\ud569\ub2c8\ub2e4.\n<\/p>\n\uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\uc758 \uad6c\uc870<\/h3>\n
\n
\ubb38\uc81c \uc18c\uac1c<\/h2>\n
\ubb38\uc81c \uc124\uba85<\/h3>\n
\n
\uc785\ub825 \ud615\uc2dd<\/h3>\n
N<\/code>\uacfc \ucffc\ub9ac\uc758 \uc218 M<\/code>\uc774 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4. (1 \u2264 N \u2264 100,000, 1 \u2264 M \u2264 100,000)
\n \uc774\ud6c4 N<\/code>\uac1c\uc758 \uc815\uc218\uac00 \ubc30\uc5f4\uc5d0 \uc8fc\uc5b4\uc9c0\uba70, \uc774\ud6c4 M<\/code>\uac1c\uc758 \ucffc\ub9ac\uac00 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.\n<\/p>\n\n
\uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\uc758 \uad6c\ud604<\/h2>\n
\nusing System;\n\nclass SegmentTree\n{\n private int[] tree;\n private int size;\n\n public SegmentTree(int n)\n {\n size = n;\n tree = new int[n * 4]; \/\/ \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\uc758 \ud06c\uae30\n }\n\n \/\/ \ud2b8\ub9ac \uad6c\ucd95\n public void Build(int[] arr, int node, int start, int end)\n {\n if (start == end)\n {\n tree[node] = arr[start]; \/\/ \ub9ac\ud504 \ub178\ub4dc\n }\n else\n {\n int mid = (start + end) \/ 2;\n Build(arr, node * 2, start, mid); \/\/ \uc67c\ucabd \uc790\uc2dd\n Build(arr, node * 2 + 1, mid + 1, end); \/\/ \uc624\ub978\ucabd \uc790\uc2dd\n tree[node] = tree[node * 2] + tree[node * 2 + 1]; \/\/ \ubd80\ubaa8 \ub178\ub4dc \uc5c5\ub370\uc774\ud2b8\n }\n }\n\n \/\/ \uad6c\uac04 \ud569 \ucffc\ub9ac\n public int Query(int node, int start, int end, int l, int r)\n {\n if (r < start || end < l)\n {\n return 0; \/\/ \ud569\uc744 \uad6c\ud560 \uc218 \uc5c6\ub294 \uad6c\uac04\n }\n\n if (l <= start && end <= r)\n {\n return tree[node]; \/\/ \uc644\uc804 \ud3ec\ud568\n }\n\n int mid = (start + end) \/ 2;\n int leftSum = Query(node * 2, start, mid, l, r);\n int rightSum = Query(node * 2 + 1, mid + 1, end, l, r);\n return leftSum + rightSum; \/\/ \ub450 \uad6c\uac04\uc758 \ud569 \ubc18\ud658\n }\n\n \/\/ \uc5c5\ub370\uc774\ud2b8\n public void Update(int node, int start, int end, int idx, int val)\n {\n if (start == end)\n {\n tree[node] = val; \/\/ \ub9ac\ud504 \ub178\ub4dc \uc5c5\ub370\uc774\ud2b8\n }\n else\n {\n int mid = (start + end) \/ 2;\n if (start <= idx && idx <= mid)\n {\n Update(node * 2, start, mid, idx, val); \/\/ \uc67c\ucabd \uc790\uc2dd \uc5c5\ub370\uc774\ud2b8\n }\n else\n {\n Update(node * 2 + 1, mid + 1, end, idx, val); \/\/ \uc624\ub978\ucabd \uc790\uc2dd \uc5c5\ub370\uc774\ud2b8\n }\n tree[node] = tree[node * 2] + tree[node * 2 + 1]; \/\/ \ubd80\ubaa8 \ub178\ub4dc \uc5c5\ub370\uc774\ud2b8\n }\n }\n}\n\nclass Program\n{\n static void Main(string[] args)\n {\n int N, M;\n N = int.Parse(Console.ReadLine());\n M = int.Parse(Console.ReadLine());\n\n int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);\n SegmentTree segTree = new SegmentTree(N);\n segTree.Build(arr, 1, 0, N - 1); \/\/ \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac \uad6c\ucd95\n\n for (int i = 0; i < M; i++)\n {\n string[] query = Console.ReadLine().Split(' ');\n int type = int.Parse(query[0]);\n\n if (type == 1)\n {\n \/\/ \uad6c\uac04 \ud569 \ucffc\ub9ac\n int l = int.Parse(query[1]) - 1;\n int r = int.Parse(query[2]) - 1;\n Console.WriteLine(segTree.Query(1, 0, N - 1, l, r));\n }\n else if (type == 2)\n {\n \/\/ \uc5c5\ub370\uc774\ud2b8\n int x = int.Parse(query[1]) - 1;\n int y = int.Parse(query[2]);\n segTree.Update(1, 0, N - 1, x, y);\n }\n }\n }\n}\n<\/code><\/pre>\n\ucf54\ub4dc \uc124\uba85<\/h2>\n
\n \uac01 \uba54\uc11c\ub4dc\uc640 \ud074\ub798\uc2a4\uc5d0 \ub300\ud55c \uc124\uba85\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:\n<\/p>\n\ud074\ub798\uc2a4 \ubc0f \ubcc0\uc218\ub97c \uc124\uba85<\/h3>\n
\n
SegmentTree<\/code>: \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub97c \ub098\ud0c0\ub0b4\ub294 \ud074\ub798\uc2a4\uc785\ub2c8\ub2e4. \ubc30\uc5f4\uc744 \ubc1b\uc544 \ud2b8\ub9ac\ub97c \uad6c\ucd95\ud558\uace0, \uad6c\uac04 \ud569 \ucffc\ub9ac\uc640 \uc5c5\ub370\uc774\ud2b8\ub97c \ucc98\ub9ac\ud569\ub2c8\ub2e4.<\/li>\ntree<\/code>: \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\uc758 \ubc30\uc5f4\uc785\ub2c8\ub2e4. \ubc30\uc5f4\uc758 \ucd5c\ub300 \ud06c\uae30\ub294 N * 4<\/code>\uc785\ub2c8\ub2e4.<\/li>\nBuild<\/code>: \uc8fc\uc5b4\uc9c4 \ubc30\uc5f4\ub85c\ubd80\ud130 \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub97c \uad6c\ucd95\ud558\ub294 \uba54\uc11c\ub4dc\uc785\ub2c8\ub2e4.<\/li>\nQuery<\/code>: \uc8fc\uc5b4\uc9c4 \uad6c\uac04\uc5d0 \ub300\ud55c \ud569\uc744 \ubc18\ud658\ud558\ub294 \uba54\uc11c\ub4dc\uc785\ub2c8\ub2e4.<\/li>\nUpdate<\/code>: \uc8fc\uc5b4\uc9c4 \uc778\ub371\uc2a4\uc758 \uac12\uc744 \uc5c5\ub370\uc774\ud2b8\ud558\uace0, \uc774\uc5d0 \ub530\ub978 \ubcc0\uacbd\uc0ac\ud56d\uc744 \ud2b8\ub9ac\uc5d0 \ubc18\uc601\ud558\ub294 \uba54\uc11c\ub4dc\uc785\ub2c8\ub2e4.<\/li>\n<\/ul>\n\uba54\uc778 \ud568\uc218 \uc124\uba85<\/h3>\n
\n \uad6c\uac04 \ud569\uc744 \uacc4\uc0b0\ud558\uac70\ub098 \uc5c5\ub370\uc774\ud2b8\ub97c \uc218\ud589\ud569\ub2c8\ub2e4.\n<\/p>\n\uacb0\ub860<\/h2>\n
\n \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub294 \uad6c\uac04 \ucffc\ub9ac\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \ucc98\ub9ac\ud560 \uc218 \uc788\ub294 \uac15\ub825\ud55c \ub3c4\uad6c\uc774\uba70, \uc5ec\ub7ec \ubb38\uc81c\uc5d0 \uc801\uc6a9 \uac00\ub2a5\ud569\ub2c8\ub2e4.
\n \ubcf5\uc7a1\ud55c \ucffc\ub9ac\ub098 \uc5c5\ub370\uc774\ud2b8\uac00 \uc694\uad6c\ub418\ub294 \ubb38\uc81c\uc5d0 \uc9c1\uba74\ud588\uc744 \ub54c, \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub97c \uace0\ub824\ud574\ubcf4\ub294 \uac83\uc774 \uc88b\uc2b5\ub2c8\ub2e4.
\n \ub2e4\uc591\ud55c \uc5f0\uc2b5 \ubb38\uc81c\ub97c \ud480\uc5b4\ubcf4\uba70 \uc774 \uc790\ub8cc\uad6c\uc870\uc758 \uc774\ud574\ub97c \uae4a\uc774 \uc788\uac8c \ub2e4\uc9c0\uae38 \ubc14\ub78d\ub2c8\ub2e4.\n<\/p>\n