Informatica Online Judge

  구간 합 [1614 / 064E]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 270   Total Tried : 340


The Champion of this Problem (C++) : gs17033 - ms / 220byte
My Best Submission (C++) : N/A

[koistudy.net (T. HS Jeon 2016)]

Background

n개의 자료를 가지는 배열에서

주어진 구간 [l, r]의 합을 구하는 q개의 질문이 입력된다.

각 q개의 질문에 대해서 빠르게 답을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 n, q가 공백으로 구분되어 입력된다.

두 번째 줄에 n개의 자료가 공백으로 구분되어 입력된다.

다음 줄부터 q줄에 걸쳐서 l, r이 공백으로 구분되어 한 줄에 하나씩 입력된다.

[입력값의 정의역]
1 <= n <= 100,000
1 <= q <= 100,000
1 <= l <= r <= n
-1,000 <= 각 원소 <= 1,000

Output

각 q개의 질문에 대해서 구간의 합을 한줄에 하나씩 출력한다.

IO Example

입력
5 3
1 2 3 4 5
1 2
3 4
1 5

출력
3
7
15

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]