树状数组

　　有这样一道题

　　已知一个数列长度为n，你需要进行w次修改一个值和q次查询一个区间内的和。

　　看起来很简单吧，但是这种题的数据范围往往很大，一般的做题，修改是O(1)的复杂度，而查询是O(n)，所以综合就是O(qn)。你可能觉得会用前缀和做起来更快，但是它的查询是O(1)，修改是O(n),所以是O(wn)，还是差不多。我们想一想，这两种方式都是要不O(1)，要不O(n)的极端情况，有没有一种方法能综合一下呢？此时，树状数组就出现了。

lowbit

　　要想使用树状数组，lowbit函数是必不可少的，他具体是什么呢？它就是用来求一个数2进制中最低一位的1，例如7=（111），所以lowbit（7）=1，又例如8=（1000），所以lowbit（8）=8.那怎么求lowbit（x）呢？这需要我们自定义了，大家记一下就行，具体原理，上网查一下吧。

1 int lowbit(x) 2 {   3     return x - (x & (x - 1));4 }

1 int lowbit(x) 2 {   3     return x & -x;4 }

实现树状数组

我们定义一个c数组（树状数组），再定义一个a数组存原本的值。

由这个图可得

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]

..............

查询前缀和

　　如果我们要查找a[3]到a[5]区间的和，我们就需要用前缀和来表示，就是a[5]+a[4]+a[3]+a[2]+a[1]-a[2]-a[1]

　　但是怎么来求a[1]-a[5]的和呢？由图得，这段和=c[5]+c[4]问题又来了，怎么由5得到4呢？好巧不巧，lowbit(5)刚好等于一，减去它正好得到4，而lowbit(4)又等于4，所以就减下去，一直到0，每次又加上这一个下标的的值，就有了a[1]-a[5]的和。

　　再来举一个例子，我们求a[1]-a[7]，这段和=c[7]+c[6]+c[4]，而怎么一步一步向下求到下标呢？lowbit(7)=1, 7-1=6, lowbit(6)=2,6-2=4 lowbit(4)=4, 4-4=0，这样，这段值就求出来了，所以这里的区间求和操作的代码也就出来了。

1 int sum(int x) 2 { 3     int ans=0; 4     while(x>0) 5     { 6         ans+=c[x]; 7         x-=lowbit(x); 8     } 9         return ans;10 }11

然后查询区间里的值就很方便了，如果求2-9，就是sum（9）-sum（2-1）

更新后缀和（单点修改）

1 void update(int x,int v)2 {3     while(x<=n)4     {5         c[x]+=v;6         x+=lowbit(x);7     }8 }

为了检验一下成果，我们来做一道水题吧

这道题我就直接贴代码了

1 #include
     
       2 #define N 500005 3 using namespace std; 4 int n,m;  5 int c[N]; 6 int lowbit(int x) 7 { 8     return x&(-x); 9 }10 void update(int x,int v)11 {12     while(x<=n)13     {14         c[x]+=v;15         x+=lowbit(x);16     }17 }18 int sum(int x)19 {20     int ans=0;21     while(x>0)22     {23         ans+=c[x];24         x-=lowbit(x);25     }26     return ans;27 }28 int main()29 {30     scanf("%d%d",&n,&m);31     for(int i=1;i<=n;i++)32     {33         int y;34         scanf("%d",&y);35         update(i,y);36     }37     for(int i=1;i<=m;i++)38     {39         int k,x,y;40         scanf("%d%d%d",&k,&x,&y);41         if(k==1)42         {43             update(x,y);44         }45         else46         {47             cout<
      
       <

然后我们看到区间修改和单点查询操作，但在这之前，我们来看一看差分

差分

　　假设有一数组a[]={2,5,9,6,4,8}，那么查分数组b[]{2,3,4,-3,-2,4};所以b[i]=a[i]-a[i-1]，

　　所以可以得出a[i]=b[1]+b[2]+b[3]+...+b[i],（这个很容易理解吧）

　　我么假设区间[2,4]都加上3，然后a[]={2,8,12,9,4,8},b[]={2,6,4,-3,-5,4}

　　不难看出，b数组只有b[2]加上了3，然后b[4+1]减去了3，

　　所以如果区间[x,y]加上z就是b[x]+z,b[y+1]-z,

　　然后我们就把b数组设为树状数组，每次区间修改就等于只进行两次单点修改，每次单点查询只需要这个点树状数组的前缀和（差分）加上他原来的值就可以了。

　　为了检验一下成果，我们又来做一道水题吧

1 #include
     
       2 using namespace std; 3 int tree[500005];//差分数组（树状数组）  4 int num[500005];//原来的值  5 int n,m; 6 int lowbit(int x) 7 { 8     return x&(-x); 9 }10 void update(int x,int v)11 {12     while(x<=n)13     {14         tree[x]+=v;15         x+=lowbit(x);16     }17 }18 int sum(int x)19 {20     int ans=0;21     while(x>0)22     {23         ans+=tree[x];24         x-=lowbit(x);25     }26     return ans;27 }28 int main()29 {30     scanf("%d%d",&n,&m);31     for(int i=1;i<=n;i++)32     {33         scanf("%d",&num[i]);34     }35     while(m--)36     {37         int x,y,k,v;38         scanf("%d",&k);39         if(k==1)40         {41             scanf("%d%d%d",&x,&y,&v);42             update(x,v);43             update(y+1,-v);    44         }45         else46         {47             scanf("%d",&x);48             cout<
      
       <

好啦，学完了树状数组，又感觉自己变强了呢，多练习一下之后，可以去了解一下线段树（和树状数组差不多）

转载于:https://www.cnblogs.com/hualian/p/11208730.html

你可能感兴趣的文章