树状数组总结

发布于 2018-12-06  51 次阅读


 

树状数组总结

树状数组是一个类似于线段树的树状结构,它通过存储一定区间内的元素来达到快速插入、快速求和的效果。并且可以节省时间,节省空间,减少代码量,可谓是非常优秀的一个树形结构

方格中数字代表对应数组的第几个元素,下排是a数组,其上方的是e数组,最下的二进制则是对应编号的二进制表示.

可以观察到,树状数组把一个数组内的元素进行了一定的二分,并存储某些元素的和,使树的深度达到了logn,这样不论是对于查找还是插入都进行了极大的优化

      每个数所指向的元素个数为1+它的二进制末尾0的个数我们把二进制中最后一个一出现的位置叫做lowbit,每个元素指向的下一个元素为x+lowbit(x),现在要修改整棵树就比较容易了。

 

  1. 累加操作
void add(int x,int t)

 {

       while(x<=n){

              e[x]+=t;

              x=x+lowbit(x);

       }

 }

 

  1. 求和操作
    int sum(int x)
    
     {
    
           int s=0;
    
           while(x>0)
    
           {
    
                  s+=e[x];
    
                  x-=lowbit(x);
    
           }
    
           return s;
    
     }