首页 > 代码库 > 树状数组

树状数组

技术分享

c为树状数组,c[i]存储i-lowbit[i]+1到i的数组的值

c[x+ lowbit(x)]为c[x]的父亲节点

http://cogs.pro/cogs/problem/problem.php?pid=264

/****************************************************************************************************                                            树状数组                         ********************************************************************************************************/#include<cstdio>const int N = 100000;int c[100005];//c为树状数组 int lowbit(int x){    return x&(-x);}void add(int x,int num){    while(x<=N){        c[x]+=num;        x+=lowbit(x);//x+ lowbit(x)为x的父亲节点     }}int sum(int x){    int ans=0;    while(x){        ans+=c[x];        x-=lowbit(x);//c[i]存储i-lowbit[i]+1到i的数组的值,所以求前缀和要不断去掉最后一位     }    return ans;}int main(){    freopen("shulie.in","r",stdin);    freopen("shulie.out","w",stdout);    int n,m,x,a,b;    char s[5];    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%d",&x);        add(i,x);    }    scanf("%d",&m);    for(int i=0;i<m;i++){        scanf("%s%d%d",s,&a,&b);        if(s[0]==S)printf("%d\n",sum(b)-sum(a-1));        else add(a,b);    }    return 0;}

 

树状数组