1. \uc11c\ub860<\/h2>\n
\n \uc548\ub155\ud558\uc138\uc694. \uc774\ubc88 \uc2dc\uac04\uc5d0\ub294 \ucf54\ud2c0\ub9b0\uc73c\ub85c \uad6c\uac04 \ud569\uc744 \ud6a8\uc728\uc801\uc73c\ub85c \uad6c\ud558\ub294 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \n \uc8fc\uc5b4\uc9c4 \uc218\uc5f4 \n \uac01 \ucffc\ub9ac\uc5d0 \ub300\ud55c \uacb0\uacfc\ub97c \ud55c \uc904\uc5d0 \ud558\ub098\uc529 \ucd9c\ub825\ud569\ub2c8\ub2e4.\n <\/p>\n \n \uad6c\uac04 \ud569\uc744 \uad6c\ud558\ub294 \uc5ec\ub7ec \uac00\uc9c0 \ubc29\ubc95\uc774 \uc788\uc9c0\ub9cc, \uae30\ubcf8\uc801\uc778 \uc811\uadfc \ubc29\ubc95\uc740 \ub2e4\uc74c \ub450 \uac00\uc9c0\uc785\ub2c8\ub2e4.\n <\/p>\n \n \uac00\uc7a5 \uc9c1\uad00\uc801\uc778 \ubc29\ubc95\uc740, \uac01 \ucffc\ub9ac\uc5d0 \ub300\ud574 \uc815\uc758\ub41c \ubc94\uc704\uc5d0\uc11c \uc9c1\uc811 \ud569\uc744 \uacc4\uc0b0\ud558\ub294 \uac83\uc785\ub2c8\ub2e4. \ud558\uc9c0\ub9cc \uc774 \ubc29\ubc95\uc740 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\uac00 O(N)\uc774\uace0, \ucd5c\ub300 \ucffc\ub9ac\uac00 100,000\uac1c\uc77c \uacbd\uc6b0 \ucd5c\uc545\uc758 \uacbd\uc6b0 O(N * M) = O(10^10)\ub85c \ub9e4\uc6b0 \ube44\ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.\n <\/p>\n \n \uc544\ub798\uc758 \ubc29\ubc95\ub860\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud6a8\uc728\uc801\uc73c\ub85c \uad6c\uac04 \ud569\uc744 \uacc4\uc0b0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \n \ub204\uc801 \ud569 \ubc30\uc5f4\uc744 \uc0ac\uc6a9\ud55c \uad6c\uac04 \ud569 \uacc4\uc0b0 \uc54c\uace0\ub9ac\uc998\uc744 \ucf54\ud2c0\ub9b0\uc73c\ub85c \uad6c\ud604\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n \n \uc704\uc758 \uad6c\ud604\uc5d0\uc11c \ud575\uc2ec\uc740 \n \uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \ubd84\uc11d\ud574\ubcf4\uba74 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4.\n <\/p>\n \n \ub530\ub77c\uc11c \uc8fc\uc5b4\uc9c4 \uc81c\uc57d \uc870\uac74 \ud558\uc5d0\uc11c \uc6b0\ub9ac\ub294 \ud6a8\uc728\uc801\uc73c\ub85c \uad6c\uac04 \ud569\uc744 \uacc4\uc0b0\ud560 \uc218 \uc788\uac8c \ub429\ub2c8\ub2e4.\n <\/p>\n<\/section>\n \n \uc704 \uc608\uc81c\uc5d0\uc11c \uc785\ub825\uc73c\ub85c \uc8fc\uc5b4\uc9c4 \ucffc\ub9ac\uc758 \uacb0\uacfc\ub294 1\ubd80\ud130 3\uae4c\uc9c0\uc758 \ud569\uc740 6, 2\ubd80\ud130 5\uae4c\uc9c0\uc758 \ud569\uc740 14, \n \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uad6c\uac04 \ud569\uc744 \uacc4\uc0b0\ud558\ub294 \ub2e4\uc591\ud55c \ubc29\ubc95\uacfc \uadf8\uc5d0 \ub530\ub978 \uc815\ud655\ud55c \uad6c\ud604\uc744 \uc0b4\ud3b4\ubcf4\uc558\uc2b5\ub2c8\ub2e4. <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
\n \ucf54\ub529\ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ub4f1\uc7a5\ud558\ub294 \ubb38\uc81c \uc911 \ud558\ub098\ub85c, \uc8fc\uc5b4\uc9c4 \uc218\uc5f4\uc758 \ud2b9\uc815 \uad6c\uac04\uc5d0 \ub300\ud55c \ud569\uc744 \uad6c\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4.
\n \uc774 \uacfc\uc815\uc744 \ud1b5\ud574 \uad6c\uac04 \ud569\uc744 \ud574\uacb0\ud558\uae30 \uc704\ud55c \ub2e4\uc591\ud55c \ubc29\ubc95\uacfc \uadf8\uc5d0 \ub530\ub978 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\uc5d0 \ub300\ud574 \ub17c\uc758\ud558\ub3c4\ub85d \ud558\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n<\/section>\n2. \ubb38\uc81c \uc124\uba85<\/h2>\n
A<\/code>\uc640 \ucffc\ub9ac Q<\/code>\uac00 \uc788\uc744 \ub54c, \uac01 \ucffc\ub9ac\ub294 \ub450 \uc815\uc218 L<\/code>\uacfc R<\/code>\ub85c \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.
\n \uc6b0\ub9ac\ub294 L<\/code>\ubd80\ud130 R<\/code>\uae4c\uc9c0\uc758 \ud569\uc744 \ube60\ub974\uac8c \uad6c\ud574\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n\uc785\ub825<\/h3>\n
\n
N<\/code>\uacfc \ucffc\ub9ac\uc758 \uac1c\uc218 M<\/code>\uc774 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.<\/li>\nN<\/code>\uac1c\uc758 \uc815\uc218\uac00 \uc8fc\uc5b4\uc838 \uc218\uc5f4 A<\/code>\ub97c \uc774\ub8f9\ub2c8\ub2e4.<\/li>\nM<\/code>\uac1c\uc758 \uc904\ub9c8\ub2e4 L<\/code>\uacfc R<\/code>\uc774 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.<\/li>\n<\/ul>\n\ucd9c\ub825<\/h3>\n
\uc81c\ud55c<\/h3>\n
\n
1 \u2264 N \u2264 100,000<\/code><\/li>\n1 \u2264 M \u2264 100,000<\/code><\/li>\n-1,000,000,000 \u2264 A[i] \u2264 1,000,000,000<\/code><\/li>\n<\/ul>\n<\/section>\n3. \uc811\uadfc \ubc29\ubc95<\/h2>\n
3.1. \ub2e8\uc21c \ubc18\ubcf5<\/h3>\n
3.2. \ub204\uc801 \ud569 \ubc30\uc5f4(Cumulative Sum Array)<\/h3>\n
\n
\n \ub204\uc801 \ud569 \ubc30\uc5f4\uc740 \ud2b9\uc815 \uc704\uce58\uae4c\uc9c0\uc758 \ud569\uc744 \ubbf8\ub9ac \uacc4\uc0b0\ud574 \ub450\ub294 \ubc30\uc5f4\ub85c, \uc120\ud615 \uc2dc\uac04 O(N)\uc73c\ub85c \ubc30\uc5f4\uc744 \ub9cc\ub4ed\ub2c8\ub2e4.
\n \uc774\ub807\uac8c \ud558\uba74 \uac01 \ucffc\ub9ac\ub97c O(1)\ub85c \ucc98\ub9ac\ud560 \uc218 \uc788\uac8c \ub429\ub2c8\ub2e4. \ub530\ub77c\uc11c \uc804\uccb4 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(N + M)\uc785\ub2c8\ub2e4.\n <\/p>\n<\/section>\n4. \uad6c\ud604<\/h2>\n
\n
\nfun main() {\n val reader = System.`in`.bufferedReader()\n val (n, m) = reader.readLine().split(\" \").map { it.toInt() }\n\n val array = reader.readLine().split(\" \").map { it.toInt() }.toIntArray()\n val sumArray = IntArray(n + 1)\n\n \/\/ \ub204\uc801 \ud569 \ubc30\uc5f4 \uc0dd\uc131\n for (i in 1..n) {\n sumArray[i] = sumArray[i - 1] + array[i - 1]\n }\n\n val result = StringBuilder()\n \/\/ \ucffc\ub9ac \ucc98\ub9ac\n repeat(m) {\n val (l, r) = reader.readLine().split(\" \").map { it.toInt() }\n val sum = sumArray[r] - sumArray[l - 1]\n result.append(sum).append(\"\\n\")\n }\n\n println(result)\n}\n<\/code>\n <\/pre>\nsumArray<\/code>\ub97c \ud1b5\ud574 \uac01 \ucffc\ub9ac\ub97c O(1)\ub85c \ucc98\ub9ac\ud560 \uc218 \uc788\ub2e4\ub294 \uc810\uc785\ub2c8\ub2e4.
\n \uad6c\uac04 [L, R]\uc758 \ud569\uc740 sumArray[R] - sumArray[L-1]<\/code>\ub85c \uc27d\uac8c \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n<\/section>\n5. \uc2dc\uac04 \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
\n
6. \uc608\uc81c<\/h2>\n
6.1. \uc785\ub825 \uc608\uc2dc<\/h3>\n
\n
\n5 3\n1 2 3 4 5\n1 3\n2 5\n1 5\n<\/code>\n <\/pre>\n6.2. \ucd9c\ub825 \uc608\uc2dc<\/h3>\n
\n
\n6\n14\n15\n<\/code>\n <\/pre>\n
\n \uc804\uccb4 1\ubd80\ud130 5\uae4c\uc9c0\uc758 \ud569\uc740 15\ub85c \uacc4\uc0b0\ub429\ub2c8\ub2e4.\n <\/p>\n<\/section>\n7. \uacb0\ub860<\/h2>\n
\n \ud2b9\ud788, \ub204\uc801 \ud569 \ubc30\uc5f4\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud6a8\uc728\uc801\uc73c\ub85c \uad6c\uac04 \ud569\uc744 \uacc4\uc0b0\ud558\ub294 \ubc29\ubc95\uc5d0 \ub300\ud574 \uae4a\uc774 \uc788\uac8c \ub17c\uc758\ud588\uc2b5\ub2c8\ub2e4.
\n \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \ub9ce\uc740 \ucf54\ub529 \ud14c\uc2a4\ud2b8 \ubb38\uc81c\uc640 \uc2e4\ubb34\uc5d0\uc11c \uc720\uc6a9\ud558\uac8c \uc0ac\uc6a9\ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \ub2e4\uc74c \uc2dc\uac04\uc5d0\ub294 \ub354 \ubcf5\uc7a1\ud55c \ub370\uc774\ud130 \uad6c\uc870\uc640 \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\ub3c4\ub85d \ud558\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n<\/section>\n<\/article>\n