二维树状数组（HD2642）

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

#define BITMAX     1002    //数组大小

typedef int valueType;    //元素类型定义

valueType BITree[BITMAX][BITMAX];    //二维树状数组，初始化

/* 2^k k表示节点编号 x 二进制末尾 0 的个数 */

inline int lowbit(int x)

{

    return x & (-x);

}

/* 节点编号不能为 0 */

/* 二维 C[x][y] = sum(A[i][j]) 其中，x-lowbit[x]+1 <= i<=x 且 y-lowbit[y]+1 <= j <=y */

inline void addPoint(int x, int y, valueType add, int n)

{

    for (int i = x; i <= n; i += lowbit(i))

        for (int j = y; j <= n; j += lowbit(j))

            BITree[i][j] += add;

}

inline valueType readSum(int x, int y)

{

    valueType sum = ;

    for (int i = x; i > ; i -= lowbit(i))

        for (int j = y; j > ; j -= lowbit(j))

            sum += BITree[i][j];

    return sum;

}

bool f[BITMAX][BITMAX];

int main()

{

    int m;

    char cc[];

    int a, b, c, d;

    scanf("%d", &m);

    memset(BITree, , sizeof(BITree));

    memset(f, false, sizeof(f));

    while (m--){

        scanf("%s", &cc);

        switch (cc[])

        {

        case 'B':

            scanf("%d %d", &a, &b);

            ++a; ++b;

            if (f[a][b]) break;

            addPoint(a, b, , BITMAX);

            f[a][b] = true;

            break;

        case 'D':

            scanf("%d %d", &a, &b);

            ++a; ++b;

            if (f[a][b]) addPoint(a, b, -, BITMAX);

            f[a][b] = false;

            break;

        case 'Q':

            scanf("%d %d %d %d", &a, &b, &c, &d);

            ++a; ++b; ++c; ++d;

            if (a > b) swap(a, b);

            if (c > d) swap(c, d);

            printf("%d\n", readSum(b, d) - readSum(b, c - ) - readSum(a - , d) + readSum(a - , c - ));

            break;

        default:

            break;

        }

    }

}