树状数组

有时需要维护一个数组的前缀和 S[i]=A[1]+A[2]+...+A[i]。但是不难发现，如果我们修改了任意一个 A[i],S[i]、 S[i+1]...S[n]都会发生变化。可以说，每次修改 A[i]后，调整前缀和 S 在最坏情况下会需要 O(n)的时间。当 n 非常大时，程序会运行得非常缓慢。因此，这里我们引入“树状数组”，它的修改与求和都是 O(logn)的，效率非常高。
(1) Add(x,d) :让A[x] 增加 d
(2) Query(L,R) :计算 A[L]+A[L+1]+A[L+2]+...+A[R];

敌兵布阵
题意:
三个操作:add(x,d),让A[x]增加d;sub(x,d),让A[x]减d;sum(x,y),计算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
题意:
二维树状数组

#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;
    }
}