The author CatShao, real name Shao Zhenxuan, OIer, Liaoning province, is only 12 years old. Thank you very much for his contribution.
Part 1 Why should I learn it?
Binary Indexed Tree, Binary Indexed Tree (BIT for short), is invented by Peter M. Fenwick in 1994 — Baidu Encyclopedia
It’s a fancy name, but what does it do?
sum
Summing is an application of tree arrays, not just summing, and this article uses summing as an example.
So now we have an array A, and we need to take the sum of different intervals in a bunch of degrees, and we need to change a random term in A bunch of times. For example, a = {0, 1, 5, 3, 2, 4}
The first time I solve for [1, 3], I get 1 + 5 + 3 = 9. The second time I solve for [2, 4], I get 5 + 3 + 2 = 10. The third time I solve for [1, 5], I get 1 + 7 + 3 + 2 + 4 = 17
[l, r] indicates the interval from the subscript L to the end of r, including L and r. l: left r: right
At this time many students think of the first method, is directly added up, isn’t it good?
But there’s a trick to this problem. We’re going to have to sum multiple times, and recalculating each time takes too long. Can we add some areas in advance and use them over and over again? This brings us to our hero, the tree array
Part 2 lowbit
The structure of the tree array is very elegant, and there is a basic operation called lowbit
Lowbit (I) can be interpreted as: the lowest 1 in I followed by 0; Or you could view it as I is divisible by n, or you could write n as 2k
One implementation of lowbit is lowbit(x) = x & x
long long lowbit(long long x) {
return x & x;
}
Copy the code
Taking 172 as an example, when we convert it to binary, we find that all the bits are different except for the 100 at the end. Using bitwise and we get the lowbit value
Part 3 Tree array
Since it’s called a tree array, it must be an array with a binary tree underneath. The exquisite structure is inseparable from lowbit, which is wonderful.
The original array is called a, the tree array is called bit, and the numbers in all three graphs are subscripts, not values.
structure
The sum of several numbers is stored in bit. We specify that the right – to – left lowbit(I) is stored in bit[I].
Bit [I] = sum from ilowbit (I) + 1 to I in array A
Changing a single value
First, changes to data can be converted to addition, which is the same as changes.
When you add them up, all you need to do to change a[I] is move them. But there may be several entries in the tree, including this a[I].
Take a[3] for example.
The values of the bits [3] and [4] corresponding to the bits [1, 4] and [8] corresponding to the bits [1, 8] and [16] corresponding to the bits [1, 16] of a need to be changedCopy the code
In the picture, we can see that 4 is on 3 heads, 8 is on 4 heads, and 16 is on 8 heads. We just need to find a way to get a block head of the block, and then use the loop to derive the whole string.
How do you find the number on your head?
The 6 in the picture has nothing to do with orange, but it’s the second set of examples
We found that we can jump to the head by adding the current block’s length to the current block’s position. I understand it this way: adding a current block will fill in the local gaps, merging into a block, which may also fill in the larger gaps, thus jumping several levels at a time
The ith block length = lowbit(I).
C + + implementation:
Void add(int index, long long value) {while (index <= n) {// Update until the largest block node[index] += value; // Update current block index += lowbit(index); // Add a length of its own, fill the gap, get the next block}}Copy the code
Range sum
Consider the sum of [1, r] by taking blocks from right to left and adding up the values represented by the blocks
Examples from the graph:
 (lowbit(13) = 1) (lowbit(13) = 1) (lowbit(13) = 1) (lowbit(13) = 1) (lowbit(13) = 1
C + + implementation
long long sum(int index) {
long long sum = 0;
while (index > 0) {
sum += node[index];
index = lowbit(index);
}
return sum;
}
Copy the code
What if the left end of the sum is not at one?
Sum (r) sum (l – 1) sum(l, r) sum(r) sum (l – 1)
structure
The above “fantasy” exists only after the tree already exists, how to construct a tree from array A (the original array)? A simple way to do this:
 Initialize all the array bits to 0
 I’m going to iterate through array A
 For each array a[I], add(I, a[I]) bit
After each add, we can make sure that the tree array is correct. After adding all of them, we can naturally build a whole tree.
Time complexity comparison
The violence below refers to the addition mentioned at the beginning.

sum

Violence: O(n) (add them up, n times)

Tree array: O(log n) (structure similar to binary tree)

To change the

Violence: O(1)

Tree array: O(log n) (one string needs to be changed, but the structure is similar to binary tree)

structure

Violence: O(n) (as read complexity)

Tree array: O(n log n) (n addition, log n each addition)
The tree array is suitable for multiple summation, multiple modification, and large amount of data.
If no modification is required, it is recommended to use prefix and, construct O(n) and sum O(1).
code
The C++ code is shown below.
BITMain case for use of the dendritic array, corresponding los valley tree array www.luogu.com.cn/problem/P33…
// // Created by Catshao on 2021/2/9. // #include <cstdio> #include <cstring> using namespace std; const long long MAX_N = 5000100; long long lowbit(long long x) { return x & x; } class BIT { public: long long node[MAX_N], n; BIT(int _n) { memset(node, 0, sizeof(node)); n = _n; } long long sum(int index) { long long sum = 0; while (index > 0) { sum += node[index]; index = lowbit(index); } return sum; } void add(int index, long long value) { while (index <= n) { node[index] += value; index += lowbit(index); }}}; int BITMain() { // https://www.luogu.com.cn/problem/P3374 int n, m, op, x, y; long long value; scanf("%d%d", &n, &m); BIT tree = BIT(n); for (int i = 1; i <= n; ++i) { scanf("%lld", &value); tree.add(i, value); } for (int i = 0; i < m; ++i) { scanf("%d%d%d", &op, &x, &y); if (op == 1) { tree.add(x, y); } else if (op == 2) { printf("%lld\n", (tree.sum(y)  tree.sum(x  1))); } } return 0; } int main() { BITMain(); }Copy the code
Reference:
 Notes on Algorithms by Hu Fan
If you have any questions, feel free to leave a comment. Thank you.