树状数组

题意：

情人节到了，小芳和小明手牵手，打算过一个完美的情人节，但是小刚偏偏也来了，当了一个明晃晃的电灯泡，小明很尴尬，就和小刚说，我交给你个任务，你完成了我俩就带你玩，否则你就回家吧。小刚很有当单身狗的觉悟，他坚决不想让小明过好情人节，同为单身狗的你能帮帮他吗？现在有一个n×n（1 <= n <= 1000）的格子，每一个格子都有一个电灯泡，可能是亮的，也可能是灭的（1代表亮， 0代表灭），现在有两种操作，一种是给你一个坐标，对于那个坐标上的灯泡，如果他是亮的，那么熄灭他，反之如果他是灭的，那么打开它。第二种操作是给你两个坐标，第一个坐标代表一个子矩阵的左上角，另一个坐标是右下角，请你求出当前子矩阵中有多少个灯泡是亮着的。燥起来吧！！！单身狗们！！！！
输入描述:
第一行两个整数，n（1 <= n <= 1000）和m（1 <= m <= 100000），分别代表正方形格子的边长和询问次数。
接下来n行，每一行有n个bool形数字（0或1），代表灯泡的状态。
接下来m行，每一行第一个数字f（1或2）代表操作的类型，如果f是1，那么接下来输入一个坐标（x, y）(1 <= x, y <= n)，对于当前位置的灯泡状态进行改变，如果是2，那么接下来输入两个坐标（x1, y1）(1 <= x1, y1 <= n)， （x2, y2）(1 <= x2, y2 <= n)，确定子矩阵的位置，输出子矩阵中亮着的灯泡数量并换行。
输出描述:
对于每一个2操作，输出子矩阵中亮着的灯泡数量并换行。

分析：

愣一看还以为是一个二维问题，想这怎么用树状数组求啊。但是，仔细看看发现这是个假的二维问题。
我们完全可以给每一行开一个树状数组嘛。记录该行区间和不就好了嘛。
吓唬人的

代码如下

#include<iostream>
#include<algorithm>
using namespace std;
const int max_n = 1100;
int graph[max_n][max_n];
int BIT[max_n][max_n];

void renew(int x, int val, int id) {
    for (;x <= max_n;x += (x & -x))BIT[id][x] += val;
}

int quiry(int x, int id) {
    int res = 0;
    for (;x;x -= (x & -x))res += BIT[id][x];
    return res;
}


int main() {
    ios::sync_with_stdio(0);
    int n, m;cin >> n >> m;
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= n;j++) {
            cin >> graph[i][j];
            if (graph[i][j])renew(j, 1, i);
        }
    for (int i = 1;i <= m;i++) {
        int t;cin >> t;
        if (t == 1) {
            int x, y;cin >> x >> y;
            if (graph[x][y] && graph[x][y]--)renew(y, -1, x);
            else if (++graph[x][y])renew(y, 1, x);
        }
        else {
            int x1, x2, y1, y2;int ans = 0;
            cin >> x1 >> y1 >> x2 >> y2;
            if (x1 > x2) { x1 = x1 ^ x2;x2 = x1 ^ x2;x1 = x1 ^ x2; }
            if (y1 > y2) { y1 = y1 ^ y2;y2 = y1 ^ y2;y1 = y1 ^ y2; }
            for (int id = x1;id <= x2;id++)
                ans += quiry(y2, id) - quiry(y1 - 1, id);
            cout << ans << endl;
        }
    }
}