The author Cat-Shao, 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 i-lowbit (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 i-th 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:

  1. Initialize all the array bits to 0
  2. I’m going to iterate through array A
  3. 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 Cat-shao 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:

  1. Notes on Algorithms by Hu Fan

If you have any questions, feel free to leave a comment. Thank you.