The focus of tree array is ontree shapearray of

Everyone knows about binary trees, right?

The leaf nodes represent the A array A[1]~A[8]

Transform now

Now define the top node C[] array of each column

As shown below

C[i] represents the sum of weights of the leaf nodes of the subtree// Here is an example of summation

You can know from the picture

C[1]=A[1];

C[2]=A[1]+A[2];

C[3]=A[3];

C[4]=A[1]+A[2]+A[3]+A[4];

C[5]=A[5];

C[6]=A[5]+A[6];

C[7]=A[7];

C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

Observe the following picture below

Convert the node number of the C[] array intobinary

1=(001) C[1]=A[1];

2=(010) C[2]=A[1]+A[2];

3=(011) C[3]=A[3];

4=(100) C[4]=A[1]+A[2]+A[3]+A[4];

5=(101) C[5]=A[5];

6=(110) C[6]=A[5]+A[6];

7=(111) C[7]=A[7];

8=(1000) C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

It can be found by comparing the formula C[i]=A[i-2^k+1]+A[i-2^k+2]+……A[i]; （k为i的二进制中从最低位到高位连续零的长度）例如i=8时，k=3;

You can bring it in for verification yourself;

Now introduce lowbit(x)

lowbit(x) actually takes out the lowest bit 1 of x. In other words The meaning of lowbit(x)=2^kk is the same as above. Let’s understand it.

Let’s talk about the code below

int lowbit(int t) {
    return t & (-t);
}
//-t 代表t的负数 计算机中负数使用对应的正数的补码来表示
//例如 :
// t=6（0110） 此时 k=1
//-t=-6=(1001+1)=(1010)
// t&(-t)=(0010)=2=2^1

C[i]=A[i-2^k+1]+A[i-2^k+2]+……A[i];

C[i]=**A[i-lowbit(i)+1]+A[i-lowbit(i)+2]+……A[i];**

Interval query

ok Next, use the C[i] array to find the sum of the first i items in the A array.

For example i=7;

sum[7]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7] ; 前i项和

C[4]=A[1]+A[2]+A[3]+A[4]; C[6]=A[5]+A[6]; C[7]=A[7];

It can be deduced: sum[7]=C[4]+C[6]+C[7];

The serial number is written in binary: sum[(111)]=C[(100)]+C[(110)]+C[(111)];

Let’s take another example i=5

sum[5]=A[1]+A[2]+A[3]+A[4]+A[5] ; 前i项和

C[4]=A[1]+A[2]+A[3]+A[4]; C[5]=A[5];

It can be deduced: sum[5]=C[4]+C[5];

The serial number is written in binary: sum[(101)]=C[(100)]+C[(101)];

A closer look at the binary tree array reveals that it is essentially a binary application.

Combine code

int getsum(int x) {
    int ans = 0;
    for(int i = x; i > 0; i -= lowbit(i))
        ans += C[i];
    return ans；
}

Demo for i=7

7 (111) ans+=C[7]

lowbit(7)=001 7-lowbit(7)=6(110) ans+=C[6]

lowbit(6)=010 6-lowbit(6)=4(100) ans+=C[4]

lowbit(4)=100 4-lowbit(4)=0(000)

Demo for i=5

5 (101) ans+=C[5]

lowbit(5)=001 5-lowbit(5)=4(100) ans+=C[4]

lowbit(4)=100 4-lowbit(4)=0(000)

single point update

How should we update the C[] array when we modify a value in the A[] array?

Think back to the process of interval query, and then look at the picture listed above

Combined with code analysis

void add(int x, int y) {
    for(int i = x; i <= n; i += lowbit(i))
        tree[i] += y;
}
//可以发现 更新过程是查询过程的逆过程
//由叶子结点向上更新C[]数组

Figure:

当更新A[1]时 需要向上更新C[1] ,C[2],C[4],C[8]

C[1], C[2], C[4], C[8]

Written as binary C[(001)],C[(010)],C[(100)],C[(1000)]

1 (001) C[1]+=A[1]

lowbit(1)=001 1+lowbit(1)=2(010) C[2]+=A[1]

lowbit(2)=010 2+lowbit(2)=4(100) C[4]**+=A[1]**

lowbit(4)=100 4+lowbit(4)=8(1000) C[8]+=A[1]

Related topics:

http://poj.org/problem?id=2299

http://codeforces.com/contest/703/problem/D

http://acm.zcmu.edu.cn/JudgeOnline/problem.php?cid=1270&pid=3

Article reproduced from:https://blog.csdn.net/Small_Orange_glory/article/details/81290634

Post Reply