算法1

二维树状数组模板题

C++ 代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int N = 1100;

int tr[N][N];

int n, m;

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

void add(int x, int y, int a)
{
    for(int i = x; i <= n; i += lowbit(i))
        for(int j = y; j <= n; j += lowbit(j))
            tr[i][j] += a;
}

int sum(int x, int y)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i))
        for(int j = y; j; j -= lowbit(j))
            res += tr[i][j];
    return res;
}

int main()
{
    scanf("%d", &n);
    int op;
    while(cin >> op, op != 3)
    {
        if(op == 1)
        {
            int x, y, k;
            scanf("%d%d%d", &x, &y, &k);
            ++ x, ++ y;
            add(x, y, k);
        }
        else if(op == 2)
        {
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            ++ x1, ++ y1, ++ x2, ++ y2;
            printf("%d\n", sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1));
        }
    }
    return 0;
}