문제 24
구간 합
길이가 $N$인 정수 수열 $A_1, A_2, \cdots, A_N$이 주어진다.
$Q$개의 쿼리를 순서대로 처리하라.
각 쿼리마다 $A_l+A_{l+1}+\cdots+A_r$을 출력하라.
입력
첫 번째 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 100\,000)$
두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-10^9 \le A_i \le 10^9)$
세 번째 줄부터 $Q$개의 줄에 걸쳐 두 정수 $l$, $r$이 공백으로 구분되어 주어진다. $(1 \le l \le r \le N)$
출력
각 쿼리마다 구간 합을 한 줄에 하나씩 출력한다.
예제 입력 1
5 4 3 -2 7 1 4 1 3 2 5 4 4 1 5
예제 출력 1
8 10 1 13
공식 해설
질의마다 구간을 직접 더하면 최악에 $O(NQ)$가 걸린다. 수열은 바뀌지 않으므로 처음부터의 합을 한 번 구해 둔다. $P_0=0$으로 두고
\[
P_i=P_{i-1}+A_i
\]
로 누적합을 계산한다.
$P_r$에서 $P_{l-1}$을 빼면 두 합에 공통으로 들어간 첫 $l-1$개 원소가 없어지고 $A_l$부터 $A_r$까지만 남는다. 따라서 각 질의의 답은 $P_r-P_{l-1}$이다. $P_0=0$으로 두었으므로 $l=1$인 경우도 같은 식을 쓴다.
전처리는 $O(N)$, 질의 하나는 $O(1)$이므로 전체 시간복잡도는 $O(N+Q)$, 공간복잡도는 $O(N)$이다. 누적합의 절댓값은 $N\cdot10^9$ 이하이므로 원소 하나보다 넓은 수의 범위를 고려해야 한다.
구현 · 언어별 풀이
C++ 구현
길이 $N+1$의 vector<long long>을 $0$으로 초기화하고 인덱스 $1$부터 누적합을 저장한다. 질의에는 prefix[r] - prefix[l - 1]을 출력한다.
C 구현
long long 누적합 배열을 $N+1$칸 만들고 s[0] = 0으로 둔다. 원소는 int로 읽어도 합은 최대 절댓값 $10^{14}$이다. 질의는 s[r] - s[l - 1]로 처리한다.
Python 구현
길이 $N+1$의 누적합을 만들고 p[r] - p[l - 1]을 출력한다. Python int는 음수 누적합과 큰 합을 그대로 처리한다.
Java 구현
long[] 누적합을 사용한다. int[]에는 합이 들어가지 않으므로 더하는 단계부터 long에 저장한다. 입력의 1-based 구간을 그대로 p[r] - p[l - 1]에 대응시킨다.
Rust 구현
Vec<i64>를 $N+1$칸 두고 prefix[0] = 0으로 시작한다. 인덱스는 usize, 값과 차이는 i64로 구분한다. $l\ge1$이므로 인덱스 $l-1$ 접근이 유효하다.
JavaScript 구현
누적합은 Float64Array(n + 1)에 저장할 수 있다. $N\le100\,000$, $\lvert A_i\rvert\le10^9$이므로 합의 절댓값은 $10^{14}$ 이하이고 Number의 안전 정수 범위 안이다. Int32Array에는 이 합이 들어가지 않는다.
$P_0=0$을 그대로 두고 p[i] = p[i - 1] + a로 채운 뒤 p[r] - p[l - 1]을 답한다. |0이나 비트 시프트로 합을 정수 변환하면 32비트로 잘리므로 쓰지 않는다.