문제 55
구간 합과 쿼리 2
길이가 $N$인 정수 수열 $A_1, A_2, \cdots, A_N$이 주어진다.
$Q$개의 쿼리를 순서대로 처리하라.
쿼리는 다음 중 하나이다.
1 i x: $A_i$에 $x$를 더한다. $(1 \le i \le N; -10^9 \le x \le 10^9)$2 l r: $A_l + A_{l+1} + \cdots + A_r$을 출력한다. $(1 \le l \le r \le N)$
입력
첫 번째 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. $(1 \le N \le 3 \cdot 10^6; 1 \le Q \le 10^6)$
두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-10^9 \le A_i \le 10^9)$
세 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.
출력
2 l r 쿼리마다 구간 합을 한 줄에 하나씩 출력한다.
예제 입력 1
5 7 1 2 3 4 5 2 1 5 1 3 10 2 2 4 1 5 -5 2 4 5 2 3 3 2 1 1
예제 출력 1
15 19 4 13 1
공식 해설
원소 하나의 덧셈과 구간 합을 빠르게 처리하기 위해 Fenwick 트리를 사용한다. 양의 정수 $i$를 나누는 가장 큰 $2$의 거듭제곱을 $b(i)$라 두고, 트리의 $i$번째 칸에 구간 $[i-b(i)+1,i]$의 합을 저장한다.
$i$번째 원소에 $x$를 더할 때는 트리의 해당 칸을 갱신하고 $i\leftarrow i+b(i)$로 이동한다. $N$ 이하인 동안 반복하면 그 원소를 포함하는 저장 구간들이 모두 갱신된다.
접두사 합 $P(r)$은 현재 위치를 $i=r$로 두고 구한다. 트리의 $i$번째 합을 더한 뒤 $i$를 $i-b(i)$로 줄이는 과정을 반복한다. $i=0$이 되면 접두사 전체를 겹치지 않게 더한 것이므로 구간 $[l,r]$의 답은 $P(r)-P(l-1)$이다.
초기 배열이 크므로 트리 구성도 선형 시간에 한다. 각 칸에 $A_i$를 놓고 $i=1$부터 $N$까지 순회하며, $i+b(i)\le N$이면 완성된 $i$번째 합을 그 위치에 더한다.
각 갱신과 조회는 $O(\log(N+1))$개의 위치를 방문한다. 전체 시간복잡도는 $O(N+Q\log(N+1))$, 공간복잡도는 $O(N)$이다. 누적합의 절댓값은 초기 원소와 갱신량을 모두 고려하여 $(N+Q)\cdot10^9$ 이하이다.
구현 · 언어별 풀이
C++ 구현
vector<long long> 하나에 트리를 저장하고 $1$ 기반 인덱스를 사용한다. $b(i)$는 i & -i로 계산한다. 초기 배열을 읽은 뒤 부모에 합을 전달하여 선형 초기화하고, 입력량이 큰 만큼 빠른 입출력을 적용한다.
C 구현
long long Fenwick tree만 두면 되고 별도의 현재 값 배열은 필요 없다. 입력을 tree에 읽고 부모로 누적해 $O(N)$에 초기화한다. 수백만 값과 백만 질의는 버퍼 입력·출력으로 처리한다.
Python 구현
tree를 array('q')로 두고 덧셈 갱신만 수행한다. 전체 입력을 split하면 토큰 객체가 대량으로 생기므로 청크 단위로 정수를 읽는다. $O(N)$ 초기화와 묶음 출력을 사용해 큰 입력 비용을 줄인다.
Java 구현
long[] tree를 사용하고 초기 합은 각 i에서 i+(i&-i)로 전달한다. 갱신이 덧셈이므로 current 배열을 복제할 이유가 없다. BufferedInputStream으로 읽고 출력도 버퍼링한다.
Rust 구현
Vec<i64> tree에 초깃값을 넣고 부모로 합을 전달한다. lowbit는 양수 usize에 wrapping_neg()를 사용해 구한다. 전체 토큰을 복사하지 않는 입력과 BufWriter 출력을 사용한다.
JavaScript 구현
초기 합의 절댓값은 $3\cdot10^{15}$ 이하이며 최대 백만 번의 증가를 모두 반영해도 $4\cdot10^{15}$ 이하이다. 따라서 Number로 정확히 계산할 수 있다. 트리에는 Float64Array를 사용하고, 합을 $32$비트로 바꾸는 연산은 하지 않는다. 이 문제에서는 큰 입력 개수만 보고 BigInt를 사용할 필요가 없다.
이전 값을 대입하는 것이 아니라 더하는 명령이므로 원래 원소 배열을 계속 보관하지 않아도 된다. 초기 값을 트리 배열에 읽은 뒤 각 위치의 합을 부모 위치로 넘기면 $O(N)$에 초기화할 수 있다.
수백만 개 토큰을 split().map(Number)로 모두 만들면 문자열·토큰·숫자 배열이 함께 남는다. fs.readSync로 일정 크기의 Buffer를 읽어 부호와 숫자를 직접 파싱하면 입력 메모리를 제한할 수 있다. Buffer 경계에서 잘린 숫자와 마지막 개행 없는 토큰도 이어서 처리해야 한다.
질의 결과도 일정 개수씩 문자열로 묶어 fs.writeSync(1, chunk)로 출력한다. 채점 핵심은 각 갱신·구간 합을 $O(\log N)$에 처리하는 Fenwick 트리이며, 빠른 입출력을 위해 다른 알고리즘이나 별도 프레임워크를 만들 필요는 없다.