二维树状数组

模板题

Nowcoder-情人节的电灯泡

#include <iostream>
using namespace std;

const int N = 1010;
int n, m;
int a[N][N], c[N][N];

int lowbit (int x) {
    return x & -x;
}
void add (int x, int y, int val) { // a[x][y] += val
    for (int i = x; i <= n; i += lowbit(i))
        for (int j = y; j <= n; j += lowbit(j))
            c[i][j] += val;
}
int sum (int x, int y) {
    int res = 0;
    for (int i = x; i >= 1; i -= lowbit(i))
        for (int j = y; j >= 1; j -= lowbit(j))
            res += c[i][j];
    return res;
}

int main () {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            scanf("%d", &a[i][j]);
            if (a[i][j] == 1) add(i, j, 1);
        }
    }

    while (m --) {
        int opt;
        scanf("%d", &opt);
        if (opt == 1) {
            int x, y;
            scanf("%d%d", &x, &y);
            if (a[x][y] == 1) {
                a[x][y] = 0;
                add(x, y, -1);
            } else {
                a[x][y] = 1;
                add(x, y, 1);
            }
        } else {
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            int res = sum(x2, y2)
                - sum(x2, y1 - 1)
                - sum(x1 - 1, y2)
                + sum(x1 - 1, y1 - 1);
            printf("%d\n", res);
        }
    }
    return 0;
}