펜윅 트리
https://www.acmicpc.net/problem/2042
2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
펜윅 트리는 구간의 합은 아니고 누적합만 구할 수 있다.
다만 변경하는 것 때문에 prefix sum 이나 suffix sum 을 대신해서 사용된다.
세그먼트 트리를 합에 대해서만 대체 적용 가능하다. (최소, 최대, 곱 등은 세그 트리를 사용해야 한다.)
합에 대해서는 세그 트리보다 훨씬 빠르다. (비재귀이고, 오른쪽 노드가 없다는 전제로 구현이 된다.)
bit 연산을 이용해서
13 일 경우 이진수(1101) 이고
13 & (-13) --> (1101) & (0001) ---> (0001) 이 되므로 tree[13] 에는 1개의 값만 저장된다.
12 일 경우 이진수 (1100) 이고
12 & (-12) --> (1100) & (0100) --> (0100) 이 되므로 tree[12] 에는 4개의 값이 저장된다.
8 일 경우는 이진수 (1000) 이고
8 & (-8) --> (1000) & (1000) --> (1000) 이 되므로 tree[8] 에는 8개의 값이 저장 된다.
그러면, tree[1 - 13] 까지의 값을 구하기 위해서는
index = 13;
while(index > 0){
res += tree[index];
index -= (index & -index);
}
이 작업만 하면 위 3가지 경우가 모두 더해져서 tree[1-13] 까지의 누적 합을 구할 수 있다.
갱신하는 작업은 계속 index 를 늘려가면 되므로 누적합 구하는 방식의 역으로 진행된다.
index = 13;
while(index > 0){
tree[index] += change
index += (index & -index);
}
#include <iostream>
using namespace std;
const int MAX = 1e6 + 7;
int N, M, K;
long long arr[MAX];
long long tree[MAX];
void update(int i, long long val) {
while (i <= N) {
tree[i] += val;
i += (i&-i);
}
}
long long sum(int i) {
long long ret = 0;
while (i > 0) {
ret += tree[i];
i -= (i&-i);
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> M >> K;
for (int i = 1; i <= N; i++) {
cin >> arr[i];
update(i, arr[i]);
}
for (int i = 0; i < M + K; i++) {
long long a, b, c; cin >> a >> b >> c;
if (a == 1) {
long long diff = c - arr[b];
arr[b] = c;
update(b, diff);
}
else {
cout << sum(c) - sum(b-1) << "\n";
}
}
return 0;
}