Binary Indexed Tree
1. Introduction
- A standard Binary Indexed Tree supports point updates and range queries.
- The aggregation operation must be associative and admit an inverse operation. Addition and xor qualify; multiplication also works when the relevant values are invertible.
- A difference array makes range updates possible.
2. Principle
Split an interval of length n into at most log n intervals.
This representation makes many operations faster. To compute the sum of a[1…7], jump backward from c[7]. c[7] covers a[7], c[6] covers a[5…6], and c[4] covers a[1…4]. The next jump would be c[0], which does not exist, so the answer is c[7]+c[6]+c[4].
For a query on a[4…7], subtract the query for a[1…3] from the query for a[1…7].
2.1 Covered Intervals
The question is: how long is the interval covered by c[x], or how far does it extend to the left?
Define the length covered by c[x] as 2 to the power of k, where:
- k is the bit position of the least significant 1 in the binary representation of x.
- 2 to the power of k is the decimal value formed by that least significant 1 and its trailing zeros in x’s binary representation.
For example, consider the interval covered by c[88]:
88 in decimal is 01011000 in binary. The least significant 1 with its trailing zeros is 1000 in binary, or 8 in decimal. Thus the length is 8 and c[88] covers a[81…88].
Use lowbit(x) to obtain the least significant 1 and its trailing zeros in x. Its decimal value is 2 to the power of k, which is the interval length, so c[x] covers a[x-lowbit(x)+1…x].
2.2 How lowbit Works
Sign-magnitude representation: the simplest machine-number representation. The highest bit is the sign bit; 1 means negative and 0 positive, while the remaining bits store the binary absolute value.
One’s complement: a positive number is unchanged; for a negative number, invert every bit except the sign bit.
1110(-1) + 1101(-2) = 1011(-4), but the correct answer should be -3;
1110(-1) + 1100(-3) = 1010(-5), but the correct answer should be -4.
The result is one away from the correct answer, which motivates the use of two’s complement.
Two’s complement: a positive number is unchanged; a negative number is its one’s complement plus 1.
lowbit(x) = x & -x. In a two’s-complement representation, -x is obtained by taking the one’s complement of x and adding 1.
This operation obtains the least significant 1 and the zeros following it.
int lowbit(int x) {
return x & -x;
}
3. Implementation
3.1 Range Queries
Any query on [L, R] can be decomposed into queries on [1, L-1] and [1, R], then subtract the former from the latter.
To query the sum of a[1…x]:
- Jump backward from c[x], which covers a[x-lowbit(x)+1…x].
- Set x -= lowbit(x); when x = 0, the process has reached the end.
- Sum the c values reached.
int query(int x) {
int sum = 0;
while(x >= 1) {
sum += c[x];
x -= lowbit(x);
}
return sum;
}
3.2 Point Updates
For a sequence of length n, modifying element x affects not only that element but also every c interval containing it.
Starting at x, find and update every c interval that contains this element.
void update(int x, int k) { // 将第x个元素加上k
while(x <= n) {
c[x] += k;
x += lowbit(x);
}
}
4. Complexity
The space complexity is O(n).
Time complexity:
- A query visits at most O(log n) intervals, because a sequence of length n is split into log n intervals.
- An update likewise visits at most O(log n) nodes: repeatedly adding lowbit(x) moves upward through intervals whose lengths are powers of two.
5. Examples
Example 1: Luogu P3374, Template 1
Point updates and range sums; the template code follows.
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, a;
int t[500010];
int lowbit(int x) {
return x & (-x);
}
void update(int x, int k) {
while(x <= n) {
t[x] += k;
x += lowbit(x);
}
}
int query(int x) {
int sum = 0;
while(x >= 1) {
sum += t[x];
x -= lowbit(x);
}
return sum;
}
signed main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a;
update(i, a);
}
int op, x, y;
while(m--) {
cin >> op;
if(op == 1) {
cin >> x >> y;
update(x, y);
} else {
cin >> x >> y;
cout << query(y) - query(x-1) << "\n";
}
}
return 0;
}
Example 2: Luogu P3368, Template 2
Range updates and point queries, using a difference array.
a[] 1 5 4 2 3
d[] 1 4 -1 -2 -1
To add 2 on [2, 4], ordinary differences use d[2] += 2 and d[5] -= 2.
How does this combine with a Binary Indexed Tree? Convert the original array to a difference array and operate on it; the problem then becomes identical to Template 1. Make point updates to the difference array, and query the sum on 1…x to recover element x.
The three helper functions are the same as in Template 1. The difference in main is converting the original array into a difference array.
int main() {
input();
d[1] = a[1];
for(int i = 2; i <= n; i++) // 差分
d[i] = a[i] - a[i-1];
for(int i = 1; i <= n; i++) // 差分数组上建树
update(i, d[i]);
int op, x, y, k;
while(m--) {
cin >> op;
if(op == 1) {
cin >> x >> y >> k;
update(x, k);
update(y+1, -k); // 利用差分来修改
} else {
cin >> x;
cout << query(x) << "\n";
}
}
return 0;
}
Example 3: Luogu P1908, Inversion Pairs
Task: for each element in a sequence of length n, count the preceding elements that are greater than it.
input output
6 11
5 4 2 6 3 1
Idea: maintain a bucket array recording the occurrence count of each value. Read the sequence from left to right; after calculating an element’s contribution, place it into the bucket array.
For example, the bucket array below corresponds to the sample original array:
i 1 2 3 4 5 6
t[] 0 1 1 1 1 1
At this point, 3 has just been placed into the array. Every value except 1 has appeared once. To find 3’s contribution, note that 5, 4, and 6 have already appeared and are greater than 3, so the contribution is 3. In the bucket array, these values lie after 3; summing their bucket values gives t[4] + t[5] + t[6] = 3. This is a range-sum query, so a Binary Indexed Tree applies.
Because values are read from left to right, the bucket array records only elements already seen. Values to the current element’s right have not yet been read and cannot affect the answer, which counts greater elements to its left.
There is a common bucket-array problem here: values may be as large as 1e9, so the bucket cannot be allocated directly. Use coordinate compression.
for(int i = 1; i <= n; i++)
cin >> a[i], b[i] = a[i];
sort(b+1, b+1+n);
int cnt = 0;
for(int i = 1; i <= n; i++)
if(i == 1 || b[i] != b[i-1])
c[++cnt] = b[i]; // 去重
for(int i = 1; i <= n; i++)
a[i] = lower_bound(c+1, c+cnt+1, a[i]) - c;
Explanation:
- Array a is the original array and retains the original values. Preserve element order while assigning ranks.
- Sort and deduplicate b to obtain c. Sorting establishes ranks; deduplication improves compression. For example, 1,000 equal values require 1,000 ranks without deduplication but only one with it.
- For each a[i], find its position in c. In the code,
lower_bound(c+1, c+cnt+1, a[i])returns the first element in c that is greater than or equal to a[i]. - Subtract c’s base address to obtain the element’s index in c.
Example:
Original array 60 100 40 30 200
Compressed 3 4 2 1 5
Apply the method above to the compressed array to solve the problem.
Tommy Chen
If you have the same hobbies, you can contact me.
