有時(shí)需要維護(hù)一個(gè)數(shù)組的前綴和 S[i]=A[1]+A[2]+...+A[i]胸懈。但是不難發(fā)現(xiàn)更卒，如果我們修改了任意一個(gè) A[i],S[i]腐芍、 S[i+1]...S[n]都會(huì)發(fā)生變化秦躯〖希可以說(shuō)，每次修改 A[i]后夜赵，調(diào)整前綴和 S 在最壞情況下會(huì)需要 O(n)的時(shí)間明棍。當(dāng) n 非常大時(shí)，程序會(huì)運(yùn)行得非常緩慢寇僧。因此击蹲，這里我們引入“樹(shù)狀數(shù)組”，它的修改與求和都是 O(logn)的婉宰，效率非常高歌豺。
(1) Add(x,d) :讓A[x] 增加 d
(2) Query(L,R) :計(jì)算 A[L]+A[L+1]+A[L+2]+...+A[R];

敵兵布陣
題意:
三個(gè)操作:add(x,d),讓A[x]增加d;sub(x,d),讓A[x]減d;sum(x,y),計(jì)算A[x]+A[x+1]+...+A[y]
題解:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define mid ((l+r)>>1)
using namespace std;
const int MAXN = 50010;
int c1[MAXN],n;
int lowbit(int x)
{
    return x&(-x);
}
int sum(int x)
{
    int res=0;
    while(x>0)
    {
        res+=c1[x];
        x-=lowbit(x);
    }
    return res;
}
void add(int x,int val)
{
    while(x<=n)
    {
        c1[x]+=val;
        x+=lowbit(x);
    }
}
int main()
{
    int t,m,val,x,y;
    char str[10];
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        scanf("%d",&n);
        memset(c1,0,sizeof(c1));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&val);
            add(i,val);
        }
        printf("Case %d:\n",cas);
        while(true)
        {
            scanf("%s",str);
            if(strcmp(str,"End")==0) break;
            else if(strcmp(str,"Query")==0)
            {
                scanf("%d%d",&x,&y);
                printf("%d\n",sum(y)-sum(x-1));
            }
            else if(strcmp(str,"Add")==0)
            {
                scanf("%d%d",&x,&val);
                add(x,val);
            }
            else
            {
                scanf("%d%d",&x,&val);
                add(x,-val);
            }
        }
    }
}

Mobile phones
題意:
二維樹(shù)狀數(shù)組

#include<cstdio>
#include<string.h>
#define maxn 1030
using namespace std;
int c[maxn][maxn],n;
int lowbit(int x)
{
    return (x&(-x));
}
int sum(int x,int y)
{
    int res=0;
    int a;
    while(x>0)
    {
        a=y;
        while(a>0)
        {
            res+=c[x][a];
            a-=lowbit(a);
        }
        x-=lowbit(x);
    }
    return res;
}
void add(int x,int a,int d)
{
    int y;
    while(x<=n)
    {
        y=a;
        while(y<=n)
        {
            c[x][y]+=d;
            y+=lowbit(y);
        }
        x+=lowbit(x);
    }
}
int main()
{
    int order,x,y,d,r,t;
    while(scanf("%d",&order)!=EOF)
    {
        if(!order)
        {
            memset(c,0,sizeof(c));
            scanf("%d",&n);
        }
        else if(order==1)
        {
            scanf("%d%d%d",&x,&y,&d);
            add(x+1,y+1,d);
        }
        else if(order==2)
        {
            scanf("%d%d%d%d",&x,&y,&r,&t);
            x++;y++;r++;t++;
            printf("%d\n",sum(r,t)-sum(r,y-1)-sum(x-1,t)+sum(x-1,y-1));
        }
        else break;
    }
}