8049 : 구간 합 쿼리
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
길이 $N$인 정수 배열 $A$가 주어지고, $Q$개의 쿼리가 각각 두 인덱스 $l$, $r$ ($1 \le l \le r \le N$)을 제시합니다. 각 쿼리에 대해 $A[l] + A[l+1] + \cdots + A[r]$의 합을 출력하십시오.
[제약 조건]
• $1 \le N, Q \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• $1 \le l \le r \le N$
[제약 조건]
• $1 \le N, Q \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• $1 \le l \le r \le N$
입력 설명
첫 번째 줄에 두 정수 $N$과 $Q$ ($1 \le N, Q \le 2 \times 10^5$)가 주어집니다.
두 번째 줄에 $N$개의 정수 $A_i$ ($1 \le A_i \le 10^9$)가 주어집니다.
다음 $Q$줄에 각각 두 정수 $l$과 $r$이 주어집니다.
두 번째 줄에 $N$개의 정수 $A_i$ ($1 \le A_i \le 10^9$)가 주어집니다.
다음 $Q$줄에 각각 두 정수 $l$과 $r$이 주어집니다.
출력 설명
$Q$개의 쿼리 결과를 각 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3
1 3 5 7 9
1 3
2 4
3 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
9
15
21도움
누적합 배열 $prefix[i] = A[1] + A[2] + \cdots + A[i]$를 미리 계산하면 각 쿼리를 $O(1)$에 처리할 수 있습니다. 구간 합은 $prefix[r] - prefix[l-1]$로 구합니다.