树状数组

树状数组用来快速的求，一个数列的前n项和

struct binaryTree
{
    int c[N], NN;
    int init(int n)
    {
        mem(c, 0);
        NN = n;
    }
    int lowbit(int x)
    {
        return x & -x;
    }
    void add(int i, int k)//把a[i]+=k
    {
        while (i <= NN)
        {
            c[i] += k;
            i += lowbit(i);
        }
    }
    int sum(int n)//求1-n的和
    {
        int sum = 0;
        while (n > 0)
        {
            sum += c[n];
            n -= lowbit(n);
        }
        return sum;
    }
    int query(int l, int r)//求区间和
    {
        return sum(r) - sum(l - 1);
    }
};

vijos-1512 SuperBrother打鼹鼠(二维树状数组)

在这个“打鼹鼠”的游戏中，鼹鼠会不时地从洞中钻出来，不过不会从洞口钻进去（鼹鼠真胆大……）。洞口都在一个大小为n(n<=1024)的正方形中。这个正方形在一个平面直角坐标系中，左下角为(0,0)，右上角为(n-1,n-1)。洞口所在的位置都是整点，就是横纵坐标都为整数的点。而SuperBrother也不时地会想知道某一个范围的鼹鼠总数。这就是你的任务。

这算是二维树状数组的模板题，下面是我的模板：

• n:矩形的大小
• update(x,y,v) 给坐标(x,y)的元素加上值v
• int sum(int x1,int y1,int x2,int y2)，查询这个范围之内的矩阵中元素的和
• query(x,y)的函数返回值代表从(1,1)–>(x,y)的矩阵的数字之和
• 需要注意如果要查询的坐标中有0出现，请给坐标+1

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
const int N=1030+7;
int n;
int c[N][N];
inline int lowbit(int t)
{
    return t&(-t);
}
void update(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 query(int x,int y)
{
    int s=0;
    for (int i=x; i>0; i-=lowbit(i))
        for (int j=y; j>0; j-=lowbit(j))
            s+=c[i][j];
    return s;
}
int sum(int x1,int y1,int x2,int y2)
{
    x1--,y1--;
    return query(x2,y2)-query(x2,y1)-query(x1,y2)+query(x1,y1);
}
int main()
{
    int m,x1,y1,x2,y2,k,x,y;
    scanf("%d",&n);
    while(scanf("%d",&m)&&(m!=3))
    {
        if(m==1)
        {
            scanf("%d%d%d",&x,&y,&k);
            x++,y++;
            update(x,y,k);
        }
        else if(m==2)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1++,y1++,x2++,y2++;
            printf("%d\n",sum(x1,y1,x2,y2));
        }
    }
    return 0;
}