#What’s the problem that Binary Indexed Tree trying to solve?

Prefix Sum

Range Sum可以通过prefix sum来求得. 但BIT并不是直接solve range sum, 而是解决prefix sum的问题.

#Two Main Function in Binary Indexed Tree

getParent(x) = x - (x & (-x)), used for query
getNext(x) = x + (x & (-x)), used for update

#Why it works?

因为每个数都可以用2进制来表示, 比如:

  • 7 = 2^2 + 2^1 + 2^0
  • 10 = 2^3 + 2^1

因此可以把这些2^x 看作是binary indexed tree中的一个结点. 每个结点的parent就是当前结点去掉最右边一位1的结果, 比如:

  • 7的parent是6,6的parent是4, 4的parent是0
  • 10的parent是8,8的parent是0

那么在每次query prefix sum的时候, 从当前结点一路往上getParent, 得到的path sum就是结果.
而在每次update的时候, 从当前结点一路update getNext, 注意getNext不一定是和当前结点在一条path上(但getParent一定是一条path).

#Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class BIT {
private int[] A;
private int[] bit;
private int n;
public(int[] A) {
this.n = A.length;
this.A = A;
this.bit = new int[n];
}
public void update(int index, int value) {
int delta = value - A[index];
while (index < n) {
bit[index] += delta;
index += (index & (-index));
}
}
public int prefixSum(int index) {
int res = 0;
while (index < n) {
res += bit[index];
index -= (index & (-index));
}
return res;
}
}

#Reference:

https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
https://www.youtube.com/watch?v=WbafSgetDDk&t=980s
https://www.youtube.com/watch?v=CWDQJGaN1gY&t=1s

Comments