\n \uc548\ub155\ud558\uc138\uc694! \ud30c\uc774\uc36c \ucf54\ub529 \ud14c\uc2a4\ud2b8 \uac15\uc88c\uc5d0 \uc624\uc2e0 \uac83\uc744 \ud658\uc601\ud569\ub2c8\ub2e4. \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294
\n “\uad6c\uac04 \ud569 \uad6c\ud558\uae30 2” \ubb38\uc81c\ub97c \ub2e4\ub8f0 \uac83\uc785\ub2c8\ub2e4. \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ub370 \uc788\uc5b4
\n \uad6c\uac04 \ud569\uc744 \ud6a8\uc728\uc801\uc73c\ub85c \uacc4\uc0b0\ud558\ub294 \ubc29\ubc95\uc740 \ub9e4\uc6b0 \uc911\uc694\ud569\ub2c8\ub2e4.
\n \uc544\ub798\uc5d0\uc11c \ubb38\uc81c \uc124\uba85\uacfc \ud574\uacb0 \uacfc\uc815\uc744 \ub2e8\uacc4\ubcc4\ub85c \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n
\n \uc8fc\uc5b4\uc9c4 N\uac1c\uc758 \uc815\uc218 A[1], A[2], …, A[N]\uc774 \uc8fc\uc5b4\uc84c\uc744 \ub54c,
\n Q\uac1c\uc758 \uc9c8\uc758\uac00 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4. \uac01 \uc9c8\uc758\ub294 \ub450 \uc815\uc218 L\uacfc R\ub85c \uad6c\uc131\ub418\uba70,
\n A[L]\ubd80\ud130 A[R]\uae4c\uc9c0\uc758 \ud569\uc744 \uad6c\ud558\ub294 \uac83\uc785\ub2c8\ub2e4.
\n \ubb38\uc81c\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:\n <\/p>\n
\n\uc785\ub825 \ud615\uc2dd:<\/strong>
\n \uccab \ubc88\uc9f8 \uc904\uc5d0 \uc815\uc218 N(1 \u2264 N \u2264 100,000)\uacfc Q(1 \u2264 Q \u2264 100,000)\uac00 \uc8fc\uc5b4\uc9c4\ub2e4.
\n \ub450 \ubc88\uc9f8 \uc904\uc5d0 N\uac1c\uc758 \uc815\uc218\ub97c \uacf5\ubc31\uc73c\ub85c \uad6c\ubd84\ud558\uc5ec \uc785\ub825\ubc1b\ub294\ub2e4. |A[i]| \u2264 1,000,000
\n Q\uac1c\uc758 \uc9c8\uc758\ub294 \ub2e4\uc74c\uacfc \uac19\uc774 \uc8fc\uc5b4\uc9c4\ub2e4: \uac01 \uc9c8\uc758\ub294 \ub450 \uc815\uc218 L\uacfc R (1 \u2264 L \u2264 R \u2264 N)
\n \ub85c \uad6c\uc131\ub41c\ub2e4.\n <\/p><\/blockquote>\n\n\ucd9c\ub825 \ud615\uc2dd:<\/strong>
\n \uac01 \uc9c8\uc758\uc5d0 \ub300\ud55c A[L]\ubd80\ud130 A[R]\uae4c\uc9c0\uc758 \ud569\uc744 \ucd9c\ub825\ud55c\ub2e4.\n <\/p>\n\ubb38\uc81c\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \ud478\ub294 \ubc29\ubc95<\/h2>\n
\n \uc774\ub7ec\ud55c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \ub9e4 \uc9c8\uc758\ub9c8\ub2e4 \uad6c\uac04\uc758 \ud569\uc744 \uc9c1\uc811 \uacc4\uc0b0\ud558\ub294 \uac83\uc774
\n \uc544\ub2c8\ub77c, \ub204\uc801 \ud569 (Prefix Sum)\uc744 \uc0ac\uc6a9\ud558\ub294 \uac83\uc774 \ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.
\n \ub204\uc801 \ud569\uc740 \uae30\ubcf8\uc801\uc73c\ub85c \ud2b9\uc815 \uad6c\uac04\uc758 \ud569\uc744 \uc0c1\uc218 \uc2dc\uac04 O(1) \uc548\uc5d0 \uad6c\ud560 \uc218 \uc788\uac8c \ud574\uc90d\ub2c8\ub2e4.\n <\/p>\n\ub204\uc801 \ud569 (Prefix Sum) \uacc4\uc0b0\ud558\uae30<\/h3>\n
\n \ub204\uc801 \ud569\uc744 \uad6c\ud558\ub294 \ubc29\ubc95\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:\n <\/p>\n
\n
- \ub204\uc801 \ud569 \ubc30\uc5f4 S\ub97c \uc0dd\uc131\ud569\ub2c8\ub2e4. \uc5ec\uae30\uc11c S[i]\ub294 A[1]\ubd80\ud130 A[i]\uae4c\uc9c0\uc758 \ud569\uc744 \uc758\ubbf8\ud569\ub2c8\ub2e4.<\/li>\n
- S[0] = 0\uc73c\ub85c \ucd08\uae30\ud654\ud569\ub2c8\ub2e4. (\ud3b8\uc758\uc0c1 0\uc744 \ub450\uc5b4\uc11c S[i]\uc5d0\uc11c S[L-1]\uc744 \ube7c\ub294 \ubc29\uc2dd\uc73c\ub85c \uacc4\uc0b0\ud569\ub2c8\ub2e4.)<\/li>\n
- \uadf8 \ub2e4\uc74c S[i]\ub97c \ub2e4\uc74c\uacfc \uac19\uc774 \uacc4\uc0b0\ud569\ub2c8\ub2e4: S[i] = S[i-1] + A[i]<\/li>\n<\/ul>\n
\n \uc774\ub97c \ud1b5\ud574 S[R] – S[L-1]\ub85c \ud55c \ubc88\uc758 \ube84\uc148 \uc5f0\uc0b0\uc73c\ub85c \uad6c\uac04 \ud569\uc744 \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n
\ubb38\uc81c \ud480\uc774 \ucf54\ub4dc<\/h3>\n
\n\ndef calculate_prefix_sum(arr):\n n = len(arr)\n prefix_sum = [0] * (n + 1)\n for i in range(1, n + 1):\n prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]\n return prefix_sum\n\ndef range_sum(prefix_sum, L, R):\n return prefix_sum[R] - prefix_sum[L - 1]\n\nN, Q = map(int, input().split())\nA = list(map(int, input().split()))\nprefix_sum = calculate_prefix_sum(A)\n\nfor _ in range(Q):\n L, R = map(int, input().split())\n print(range_sum(prefix_sum, L, R))\n <\/code>\n <\/pre>\n\n \uc704\uc758 \ucf54\ub4dc\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \uacfc\uc815\uc744 \uc218\ud589\ud569\ub2c8\ub2e4:\n <\/p>\n
\n
- \uba3c\uc800, \uc8fc\uc5b4\uc9c4 \ubc30\uc5f4 A\uc758 \uae38\uc774 N\uc5d0 \ub300\ud55c \ub204\uc801 \ud569 \ubc30\uc5f4\uc744 \uacc4\uc0b0\ud558\ub294 \ud568\uc218\ub97c \ud638\ucd9c\ud569\ub2c8\ub2e4.<\/li>\n
- \uac01 \uc9c8\uc758\uc5d0 \ub300\ud574 L\uacfc R\uc744 \uc785\ub825\ubc1b\uace0, \ud574\ub2f9 \uad6c\uac04\uc758 \ud569\uc744 \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/li>\n<\/ul>\n
\uc2dc\uac04 \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
\n \uc774 \ubb38\uc81c\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \ubd84\uc11d\ud574\ubcf4\uba74 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:\n <\/p>\n
\n
- \ub204\uc801 \ud569 \ubc30\uc5f4\uc744 \uacc4\uc0b0\ud558\ub294 \ub370 O(N)\uc758 \uc2dc\uac04\uc774 \uc18c\uc694\ub429\ub2c8\ub2e4.<\/li>\n
- \uac01 \uc9c8\uc758\uc5d0 \ub300\ud55c \uad6c\uac04 \ud569\uc744 \uacc4\uc0b0\ud558\ub294 \ub370 O(1)\uc758 \uc2dc\uac04\uc774 \uc18c\uc694\ub429\ub2c8\ub2e4.<\/li>\n
- \ub530\ub77c\uc11c \uc804\uccb4 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(N + Q)\uac00 \ub429\ub2c8\ub2e4.<\/li>\n<\/ul>\n
\uacb0\ub860<\/h2>\n
\n \uad6c\uac04 \ud569 \ubb38\uc81c\ub294 \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ucd9c\uc81c\ub418\ub294 \ubb38\uc81c \uc911 \ud558\ub098\uc785\ub2c8\ub2e4.
\n \ub204\uc801 \ud569\uc744 \ud65c\uc6a9\ud558\uba74 \ubb38\uc81c\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\ub294 \uc88b\uc740 \ubc29\ubc95\uc785\ub2c8\ub2e4.
\n \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c \ub2e4\ub8ec \ub0b4\uc6a9\uc744 \ubc14\ud0d5\uc73c\ub85c \ub2e4\uc591\ud55c \ubcc0\ud615 \ubb38\uc81c\ub4e4\uc744 \ud480\uc5b4\ubcf4\ub294 \uac83\ub3c4 \uc88b\uc2b5\ub2c8\ub2e4.
\n \ucd94\uac00 \uc9c8\ubb38\uc774\ub098 \ub2e4\ub978 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc5d0 \ub300\ud574 \ub354 \uc54c\uace0 \uc2f6\ub2e4\uba74 \uc5b8\uc81c\ub4e0\uc9c0 \ub313\uae00\uc744 \ub0a8\uaca8\uc8fc\uc138\uc694!\n <\/p>\n<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"