以前就听说线段树的适用范围比树状数组要广 所以就一直没有学 昨天碰到了处理前缀和的问题 发现树状数组可以更方便 所以就有点好奇了 同样 我还是选择了看视频w

传送门：https://www.bilibili.com/video/av18735440/

参考博客：http://blog.csdn.net/largecub233/article/details/56666971

区间修改：http://blog.csdn.net/qq_21841245/article/details/43956633

模板：

（下标都从1开始）

区间查询 单点修改

int n;
int d[500010];
int lowbit(int x)
{
    return x&(-x);
}
int query(int x)//查询前缀和
{
    int res=0;
    while(x)
    {
        res+=d[x];
        x-=lowbit(x);
    }
    return res;
}
void add(int x,int v)//单点修改
{
    while(x<=n)
    {
        d[x]+=v;
        x+=lowbit(x);
    }
}
int main()
{
    int m,x,y,ope;
    scanf("%d%d",&n,&m);
    memset(d,0,sizeof(d));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        add(i,x);
    }
    while(m--)
    {
        scanf("%d%d%d",&ope,&x,&y);
        if(ope==1)add(x,y);
        else if(ope==2)printf("%d\n",query(y)-query(x-1));
    }
    return 0;
}

单点查询 区间修改

int n;
int c[500010];//差分数组
//这里运用了差分思想，假设原本的数据存在a数组中，
//那么c数组储存的就是c[i]=a[i]-a[i-1]，如果c[1]=a[1]，那么很明显
//a[i]=c[i]+c[i-1]+c[i-2]+...+c[2]+c[1].
//这样我们每次单点查询的时候只要加上c数组的前缀就可以了。
int lowbit(int x)
{
    return x&(-x);
}
int query(int x)//单点查询
{
    int res=0;
    while(x)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
void add(int x,int v)//区间修改
{
    while(x<=n)
    {
        c[x]+=v;
        x+=lowbit(x);
    }
}
int main()
{
    int m,x,y,k,ope,ls;
    scanf("%d%d",&n,&m);
    memset(c,0,sizeof(c));
    ls=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        add(i,x-ls);
        ls=x;
    }
    while(m--)
    {
        scanf("%d",&ope);
        if(ope==1)
        {
            scanf("%d%d%d",&x,&y,&k);
            add(x,k);
            add(y+1,-k);
        }
        else if(ope==2)
        {
            scanf("%d",&x);
            printf("%d\n",query(x));
        }
    }
    return 0;
}

加了区间修改的万能模板

typedef long long ll;
using namespace std;
ll n;
ll sum[200010];//原数列的前缀和
ll c[200010];//差分数组
ll ci[200010];//差分*i数组
ll lowbit(ll x)
{
    return x&(-x);
}
ll query(ll arr[],ll x)//查询前缀和
{
    ll res=0;
    while(x)
    {
        res+=arr[x];
        x-=lowbit(x);
    }
    return res;
}
void add(ll arr[],ll x,ll v)//单点修改
{
    while(x<=n)
    {
        arr[x]+=v;
        x+=lowbit(x);
    }
}
int main()
{
    long long m,x,y,k,ope;
    scanf("%lld",&n);
    memset(c,0,sizeof(c));
    sum[0]=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&x);
        sum[i]=sum[i-1]+x;
    }
    scanf("%lld",&m);
    while(m--)
    {
        scanf("%lld",&ope);
        if(ope==1)
        {
            scanf("%lld%lld%lld",&x,&y,&k);
            add(c,x,k);
            add(c,y+1,-k);
            add(ci,x,k*x);
            add(ci,y+1,-k*(y+1));
        }
        else if(ope==2)
        {
            scanf("%lld%lld",&x,&y);
            ll sum1=sum[x-1]+x*query(c,x-1)-query(ci,x-1);
            ll sum2=sum[y]+(y+1)*query(c,y)-query(ci,y);
            printf("%lld\n",sum2-sum1);
        }
    }
    return 0;
}

二维树状数组

（以bzoj1452为例）

题意：一个n*m的方格，初始时每个格子有一个整数权值。接下来每次有2种操作：

改变一个格子的权值；

求一个子矩阵中某种特定权值出现的个数。

思路：加个权值的维度即可。

代码：

int row,clo;
int mp[310][310];
int c[310][310][110];//差分数组
int lowbit(int x)
{
    return x&(-x);
}
int query(int x,int y,int z)//单点查询
{
    int res=0;
    for(int i=x;i>0;i-=lowbit(i))
        for(int j=y;j>0;j-=lowbit(j))
            res+=c[i][j][z];
    return res;
}
void add(int x,int y,int z,int v)//区间修改
{
    for(int i=x;i<=row;i+=lowbit(i))
        for(int j=y;j<=clo;j+=lowbit(j))
            c[i][j][z]+=v;
}
int main()
{
    int m,ope,x,y,z,x1,y1,x2,y2;
    scanf("%d%d",&row,&clo);
    memset(c,0,sizeof(c));
    for(int i=1;i<=row;i++)
        for(int j=1;j<=clo;j++)
        {
            scanf("%d",&mp[i][j]);
            add(i,j,mp[i][j],1);
        }
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d",&ope);
        if(ope==1)
        {
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,mp[x][y],-1);
            mp[x][y]=z;
            add(x,y,z,1);
        }
        else if(ope==2)
        {
            scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&z);
            printf("%d\n",query(x1-1,y1-1,z)+query(x2,y2,z)-query(x1-1,y2,z)-query(x2,y1-1,z));
        }
    }
    return 0;
}

（以poj2155为例）

题意：给出矩阵左上角和右下角坐标，矩阵里的元素1变0，0 变1，给出询问，问某个点是多少。

思路：

区间修改的时候，(x1,y1)为左上角的点，(x2,y2)是右下角的点。

修改的应该是add(x1,y1,1),add(x2+1,y1,-1),add(x1,y2+1,-1),add(x2+1,y2+1,1)。

代码：

int n;
int c[1010][1010];//差分数组
int lowbit(int x)
{
    return x&(-x);
}
int query(int x,int y)//单点查询
{
    int res=0;
    for(int i=x;i>0;i-=lowbit(i))
        for(int j=y;j>0;j-=lowbit(j))
            res+=c[i][j];
    return res;
}
void add(int x,int y,int v)//区间修改
{
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=n;j+=lowbit(j))
            c[i][j]+=v;
}
int main()
{
    int t,m,x,y,x1,y1,x2,y2;//左上角右下角
    char ope[5];
    scanf("%d",&t);
    for(int kase=0;kase<t;kase++)
    {
        if(kase!=0)printf("\n");
        scanf("%d%d",&n,&m);
        memset(c,0,sizeof(c));
        while(m--)
        {
            scanf("%s",ope);
            if(ope[0]=='C')
            {
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                add(x1,y1,1);
                add(x2+1,y1,-1);
                add(x2+1,y2+1,1);
                add(x1,y2+1,-1);
            }
            else if(ope[0]=='Q')
            {
                scanf("%d%d",&x,&y);
                printf("%d\n",(query(x,y))%2);
            }
        }
    }
    return 0;
}