7021 : 누적합 배열 만들기
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
정수 배열이 주어졌을 때, 특정 구간
미리 배열의 누적합(Prefix Sum)을 계산해두면, 어떤 구간의 합이라도 $O(1)$만에 구할 수 있습니다.
배열이 주어지고 여러 개의 구간 쿼리가 주어졌을 때, 각 구간의 합을 구하는 프로그램을 작성하십시오.
[제약 조건]
• 배열 크기 $N$: $1 \le N \le 100{,}000$
• 쿼리 수 $Q$: $1 \le Q \le 100{,}000$
• 배열 원소: $-10^9 \le a_i \le 10^9$
• 구간 범위: $0 \le L \le R < N$ (0-indexed)
[L, R]의 합을 빠르게 구하고자 합니다. 매번 쿼리가 들어올 때마다 구간의 합을 직접 구하면 $O(N \times Q)$의 시간이 걸려 비효율적입니다.미리 배열의 누적합(Prefix Sum)을 계산해두면, 어떤 구간의 합이라도 $O(1)$만에 구할 수 있습니다.
배열이 주어지고 여러 개의 구간 쿼리가 주어졌을 때, 각 구간의 합을 구하는 프로그램을 작성하십시오.
[제약 조건]
• 배열 크기 $N$: $1 \le N \le 100{,}000$
• 쿼리 수 $Q$: $1 \le Q \le 100{,}000$
• 배열 원소: $-10^9 \le a_i \le 10^9$
• 구간 범위: $0 \le L \le R < N$ (0-indexed)
입력 설명
첫째 줄에 배열의 크기 $N$ ($1 \le N \le 100000$)이 주어집니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다. 각 정수의 범위는 $-10^9$ 이상 $10^9$ 이하입니다.
셋째 줄에 쿼리의 개수 $Q$ ($1 \le Q \le 100000$)가 주어집니다.
넷째 줄부터 $Q$개의 줄에 걸쳐 구간을 나타내는 두 정수 $L$과 $R$이 공백으로 구분되어 주어집니다. ($0$-based 인덱스이며, $0 \le L \le R < N$)
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다. 각 정수의 범위는 $-10^9$ 이상 $10^9$ 이하입니다.
셋째 줄에 쿼리의 개수 $Q$ ($1 \le Q \le 100000$)가 주어집니다.
넷째 줄부터 $Q$개의 줄에 걸쳐 구간을 나타내는 두 정수 $L$과 $R$이 공백으로 구분되어 주어집니다. ($0$-based 인덱스이며, $0 \le L \le R < N$)
출력 설명
각 쿼리마다 배열의 $L$번째 원소부터 $R$번째 원소까지의 합($A[L] + A[L+1] + \dots + A[R]$)을 줄바꿈하여 한 줄씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
1 2 3 4 5
3
0 2
1 4
2 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
6
14
3도움
크기 $N+1$의 누적합 배열
pref를 pref[i] = A[0] + ... + A[i-1]와 같이 정의합니다. 구간 [L, R]의 합은 pref[R+1] - pref[L]로 $O(1)$에 바로 구할 수 있습니다. 합이 매우 커질 수 있으므로 자료형의 크기에 주의하십시오.