poj-1195

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/42145959

二维树状数组应用

http://poj.org/problem?id=1195

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <map>
#include <stack>

using namespace std;

int s;
int p[1030][1030];

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

void add(int a,int b,int d)
{
    for (int i = a; i <= s; i += lowbit(i))
        for (int j = b; j <= s; j += lowbit(j))
        {
            p[i][j] += d;
        }
}

int sum(int a, int b)
{
    int ans = 0;
    for (int i = a; i >0; i -= lowbit(i))
        for (int j = b; j >0; j -= lowbit(j))
        {
            ans += p[i][j];
        }
    return ans;
}

void init(int s)
{
    for (int i = 0; i <= s; i++)
        for (int j = 0; j <= s;j++)
            p[i][j] = 0;
}

int main()
{
        int d;
        while (scanf("%d", &d) != EOF)
        {
            if (d == 3)
                return 0;

            if (d == 0)
            {
                scanf("%d", &s);
                init(s);
            }


            if (d == 1)
            {
                int x, y, a;
                scanf("%d %d %d", &x, &y, &a);
                {
                    add(x + 1, y + 1, a);
                }
            }

            if (d == 2)
            {
                int l, b, r, t;
                scanf("%d %d %d %d", &l, &b, &r, &t);
                l++; b++; r++; t++;
                printf("%d\n", sum(l - 1, b - 1) + sum(r, t) - sum(r, b - 1) - sum(l - 1, t));
            }
        }
    return 0;
}