바이너리 인덱스 트리
1. 점 업데이트와 구간 합 查询
lowbit 함수
바이너리 인덱스 트리의 핵심은 lowbit 연산입니다:
lowbit(x) = x & (-x)
이 연산은 x의 이진 표현에서 가장 오른쪽에 있는 1의 위치 값을 반환합니다.
예를 들어, x = (0010010011000)₂ 라면:
-x = ~x + 1 = (1101101101000)₂
x & (-x) = (0000000001000)₂
동작 원리
배열 a[1...n]이 있을 때, 트리 배열 tree[1...n]을 다음과 같이 정의합니다:
tree[i] = a[i - lowbit(i) + 1] + a[i - lowbit(i) + 2] + ... + a[i]
즉, tree[i]는 특정 범위의 합을 저장합니다.
구간 합 계산
구간 [L, R]의 합을 구하려면:
sum(1, R) - sum(1, L-1)
1부터 x까지의 합을 구하는 알고리즘:
- x를 2진수로 변환
- ans += tree[x] (현재 구간 합累加)
- x -= lowbit(x)
- x가 0이 될 때까지 반복
점 업데이트
위치 x의 값을 v만큼 증가시킬 때, tree[x], tree[x + lowbit(x)], tree[x + 2*lowbit(x)]... 를 모두 업데이트해야 합니다.
구현 코드:
#include
using namespace std;
const int MAXN = 500000 + 5;
int tree[MAXN];
int n, m, val;
int getLowbit(int x) {
return x & (-x);
}
void update(int idx, int delta) {
for (int i = idx; i <= n; i += getLowbit(i)) {
tree[i] += delta;
}
}
int prefixSum(int idx) {
int result = 0;
for (int i = idx; i > 0; i -= getLowbit(i)) {
result += tree[i];
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> val;
update(i, val);
}
int op, x, y;
while (m--) {
cin >> op >> x >> y;
if (op == 1) {
update(x, y);
} else {
cout << prefixSum(y) - prefixSum(x - 1) << '\n';
}
}
return 0;
} 2. 구간 업데이트와 점 查询
이번에는 반대의 작업을 수행합니다. 구간 [L, R]에 값을 더하고, 특정 위치의 값을 查询합니다.
차분 배열(diff) concept을 利用합니다:
diff[i] = a[i] - a[i-1] (a[0] = 0)
구간 [L, R]에 k를 더하려면:
diff[L] += k
diff[R+1] -= k
위 쿼리 시점의 값을 구하려면 diff의 prefix sum을 구하면 됩니다.
#include
using namespace std;
const int MAXN = 500000 + 5;
int tree[MAXN];
int arr[MAXN];
int n, m;
int getLowbit(int x) {
return x & (-x);
}
void update(int idx, int delta) {
for (int i = idx; i <= n; i += getLowbit(i)) {
tree[i] += delta;
}
}
int prefixSum(int idx) {
int result = 0;
for (int i = idx; i > 0; i -= getLowbit(i)) {
result += tree[i];
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
int op, x, y, k;
while (m--) {
cin >> op >> x;
if (op == 1) {
cin >> y >> k;
update(x, k);
update(y + 1, -k);
} else {
cout << arr[x] + prefixSum(x) << '\n';
}
}
return 0;
} 3. 응용 문제들
역쌍 개수 구하기
배열에서 i < j 이고 a[i] > a[j]인 쌍의 개수를 求합니다.
#include
using namespace std;
typedef long long ll;
const int MAXN = 500000 + 5;
int n;
int arr[MAXN];
int sorted[MAXN];
int tree[MAXN];
ll answer;
int getLowbit(int x) {
return x & (-x);
}
void update(int idx) {
for (int i = idx; i <= n; i += getLowbit(i)) {
tree[i]++;
}
}
int query(int idx) {
int cnt = 0;
for (int i = idx; i > 0; i -= getLowbit(i)) {
cnt += tree[i];
}
return cnt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
sorted[i] = arr[i];
}
sort(sorted + 1, sorted + n + 1);
for (int i = 1; i <= n; i++) {
int pos = lower_bound(sorted + 1, sorted + n + 1, arr[i]) - sorted;
answer += (ll)i - 1 - (ll)query(pos);
update(pos);
}
cout << answer << '\n';
return 0;
} 트리에서의 노드 방문 순서
루트 노드에서 leaf까지의 경로에 있는 노드 개수를 구하는 问题입니다.
#include
using namespace std;
typedef long long ll;
const int MAXN = 100000 + 5;
struct Edge {
int next;
int to;
};
int n;
int head[MAXN];
int edgeCnt = 0;
int enterTime[MAXN];
int exitTime[MAXN];
int nodeValue[MAXN];
int currentTime = 0;
ll tree[MAXN];
Edge edges[MAXN * 2];
void addEdge(int u, int v) {
edges[++edgeCnt] = {head[u], v};
head[u] = edgeCnt;
}
void dfs(int node, int parent) {
enterTime[node] = ++currentTime;
for (int i = head[node]; i; i = edges[i].next) {
int to = edges[i].to;
if (to == parent) continue;
dfs(to, node);
}
exitTime[node] = currentTime;
}
int getLowbit(int x) {
return x & (-x);
}
void update(int idx, ll delta) {
for (int i = idx; i <= n; i += getLowbit(i)) {
tree[i] += delta;
}
}
ll query(int idx) {
ll sum = 0;
for (int i = idx; i > 0; i -= getLowbit(i)) {
sum += tree[i];
}
return sum;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
int u, v;
for (int i = 1; i < n; i++) {
cin >> u >> v;
addEdge(u, v);
addEdge(v, u);
}
dfs(1, 0);
for (int i = 1; i <= n; i++) {
cin >> nodeValue[i];
}
for (int i = 1; i <= n; i++) {
cout << query(enterTime[nodeValue[i]]) << '\n';
update(enterTime[nodeValue[i]], 1);
update(exitTime[nodeValue[i]] + 1, -1);
}
return 0;
} 부분 배열 합이 0 이상인 경우 수
부분 배열의 합이 0 이상인 경우의 수를 求합니다.
#include
using namespace std;
const int MOD = 1000000009;
const int MAXN = 100000 + 5;
int n;
int arr[MAXN];
int prefix[MAXN];
int sortedPrefix[MAXN];
int tree[MAXN];
int result;
int getLowbit(int x) {
return x & (-x);
}
void update(int idx, int delta) {
for (int i = idx; i <= n + 1; i += getLowbit(i)) {
tree[i] = (tree[i] + delta) % MOD;
}
}
int query(int idx) {
int sum = 0;
for (int i = idx; i > 0; i -= getLowbit(i)) {
sum = (sum + tree[i]) % MOD;
}
return sum;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
prefix[i] = prefix[i - 1] + arr[i];
sortedPrefix[i] = prefix[i];
}
sortedPrefix[0] = prefix[0] = 0;
sort(sortedPrefix, sortedPrefix + n + 1);
for (int i = 0; i <= n; i++) {
prefix[i] = lower_bound(sortedPrefix, sortedPrefix + n + 1, prefix[i]) - sortedPrefix + 1;
}
update(prefix[0], 1);
for (int i = 1; i <= n; i++) {
result = query(prefix[i]);
update(prefix[i], result);
}
cout << result % MOD << '\n';
return 0;
} 4. 정리
바이너리 인덱스 트리는 다음과 같은 경우에 유용합니다:
- 점 업데이트 + 구간 합 查询: O(log n)
- 구간 업데이트 + 점 查询: O(log n)
- 역쌍, 순위 查询 등 다양한 문제에 응용
핵심은 lowbit 연산을 통한 구간 관리입니다. 이를 이해하면 다양한 문제를 효율적으로 해결할 수 있습니다.