树状数组

刚学完树状数组，所以来写篇博客理下思路。

树状数组长这样：

树状数组

跟线段树不同，这个是每一竖列的c[i]代表每一个子树的权值（子树与他相连的左下方的部分），与线段数的长代码不同，树状数组主要靠二进制之间的某种奇妙的关系来进行

根节点的子节点如何确定呢?

看下面这些式子:

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

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

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

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

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

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

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

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

仔细观察,我们会发现他需要A[i]数字的个数和二进制末尾0的个数有关,0个数为0,需要1个,0个数为1,需要2个,0个数为3,需要8个

所以C[i]二进制末尾0的个数为k,则C[i]=A[i]+A[i-1]+...+A[i-2^k+1];

代码可以用

int lowbit(int x)
{
    return x&(-x);
}

返回的值是根据x求出的2^k(二进制末尾0的个数);

已知2^k,C[i]全部求出之后,就可以不用再用A[i]了,之后就用C[i],进行树间的更新查询操作

更新:

更新A[3]时,我们需要更新C[3]C[4]C[8]

转化成二进制:

3:0011

4:0100

8:1000

3+1=4

4+4=8

1=2^0

4=2^2

所以这个还要和我们上面讲的二进制末尾0的个数相关联(我也不知道为什么)

所以3+lowbit(3)=4

4+lowbit(4)=8

我们又要用到上面那个代码了.

知道这个之后,我么就可以进行更新操作了:

void add(int pos,int y)
{
    for(int i=pos; i<=n; i+=lowbit(i))  //确定下一个i
        val[i]+=y;  //这里是增加减少,如果是直接改值,直接写等号即可
}

查询

与更改操作相反

查询7这个节点之前所有值的和sum[7]时

sum[7]=C[7]+C[6]+C[4]

还是根据二进制

7:0111

6:0110

4:0010

7-1=6,6-2=4

7-2^0=6,6-2^1=4

观察发现,7末尾0个数为0,6末尾0个数为1;

代码:

int getsum(int x)
{
    int ans=0;
    for(int i=x; i; i-=lowbit(i))  //确定下一个根节点
        ans+=val[i];  
    return ans;
}

不管数据是不是8,都按上述操作,不影响.

结束~

根节点的子节点如何确定呢?

更新:

查询

相关推荐