数据结构----树状数组----子区间的和

3/8/2017来源:ASP.NET技巧人气:1352

一、几个问题

问题一:已知数组a[],元素个数为n,现在要求a数组中i到j区间内的和(1<=i<=j<=n)

解法1:每次查询就把i到j之间每个元素都加起来。最坏情况O(Qn)(Q为查询次数)

解法2:用前缀和数组sum[k]来记录1到k的和,查询时,就输出sum[j]-sum[i-1]。O(1)

问题二:已知数组a[],元素个数为n,现在有两种操作

1、求a数组中i到j区间内的和(1<=i<=j<=n)

2、将a数组中a[k](1<=k<=n)的值加上d。

解法1:每次查询就把i到j之间每个元素都加起来,每次更改就把a[k]加上d。最坏情况O(Qn)

解法2:用前缀和数组sum[k]来记录1到k的和,查询时,就输出sum[j]-sum[i-1],更改时,就把k到n之间的所有元素都加上d。最坏情况O(Qn)

解法3:树状数组。O(Qlog(n))

树状数组就是在这种背景下产生的。

二、树状数组的概念

利用二进制来分类,每一个数存的数据是存的一个区间,它存的区间大小,取决于它的二进制里权值最低的1权值,

如果感觉听不懂,就来看一下例子吧。

比如说6,转化成二进制位110,权值最低的1就是红色标注的那个1,它的权值是2。

再比如说12,转化成二进制位1100,权值最低的权值就是4。

求它的最低权值有一个简便算法:

int lowbit(int x)

{

return x&-x; }

接下来就是求和的操作,我们发现1~14之间的和是a[14]+a[12]+a[8],恰好是14对应二进制a[1110],a[1100],a[1000]

(以上的1110、1100、1000位二进制),于是可以发现求和算法:

int getsum(int x)

{

int sum=0;

while(x){

sum+=treearray[x];

x-=lowbit(x); } }

然后是修改操作,实际上就是找它的父亲,直到它的父亲大于n为止。

void update(int x,int d)

{

while(x<=n){

treearray[x]+=d;

x+=lowbit(x); } }

有了这三个函数,求解上面的问题就容易多了,但是要注意初始化: for(i=1;i<=n;i++){

scanf("%d",&x);

update(i,x); }

完整代码:

#include<cstdio>
int treearray[1000002],N;
int lowbit(int x)
{
    return x&-x;
}
int getsum(int x)
{
    int sum=0;
    while(x){
        sum+=treearray[x];
        x-=lowbit(x);
    }
    return sum;
}
void update(int i,int x)
{
    while(i<=N){
        treearray[i]+=x;
        i+=lowbit(i);
    }
}
int main()
{
    int Q,i,a,b,x;
    scanf("%d%d",&N,&Q);
    for(i=1;i<=Q;i++){
        scanf("%d%d%d",&x,&a,&b);
        if(x==0){
            update(a,b);
        }
        if(x==1){
            PRintf("%d\n",getsum(b)-getsum(a-1));
        }
    }
}