树状数组小结-二维

树状数组:
模板：
取数组下标二进制非0最低位所表示的值；
区间查询。
单点更新：

同一维树状数组比较，这样比较好理解；
如果一维不会可以看看我的一维树状数组博客
1.一维二维都是：取数组下标二进制非0最低位所表示的值；

int lowbit(int x)
{
    return x&(-x);
}

2. 一维树状数组更新是这样的：

void add(int x,int val)
{
    for(;x<=n;x+=lowbit(x))
    {
        num[x]+=val;
    }
}

二维树状数组更新是这样的：

void  add(int x,int y,int val)
{
    for(int i=x;i<=s;i+=lowbit(i))
    {
        for(int j=y;j<=s;j+=lowbit(j))
        {
            num[i][j]+=val;
        }
    }
}

3.一维树状数组查询是这样的：

int query(int x)
{
    int ans=0;
    for(;x>0;x-=lowbit(x))
    {
        ans+=c[i];
    }
    return ans;
}

二维树状数组查询是这样的：

int query(int x,int y)
{
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        for(int j=y;j>0;j-=lowbit(j))
        {
            ans+=num[i][j];
        }
    }
    return ans;
}

说说对二维的理解，其实就是数组的改变，变成二维呈次的形式，那么代码上是很好理解的，但和一维树状数组一样解释，就有点多余。自行理解；

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
int su[1050][1050],s;
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int y,int v)
{
    for (int i=x; i<=s; i+=lowbit(i))
        for (int j=y; j<=s; j+=lowbit(j))
            su[i][j]+=v;
}
int sum(int x,int y)
{
    int ans=0;
    for (int i=x; i>0; i-=lowbit(i))
        for (int j=y; j>0; j-=lowbit(j))
            ans+=su[i][j];
    return ans;
}
int n,m,p,x1,x2,y1,y2,tmp;
int main()
{
    while(scanf("%d",&p))
    {
        if (p==0) scanf("%d",&s);
        if (p==3) return 0;
        if (p==1)
        {
            scanf("%d%d%d",&x1,&y1,&tmp);
            x1++;
            y1++;
            add(x1,y1,tmp);
        }
        else if (p==2)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1++;
            y1++;
            x2++;
            y2++;
            int yy=sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1);
            printf("%d\n",yy);
        }
    }
    return 0;
}