思路与算法

二维树状数组维护零矩阵的单点加与矩形和。更新(x,y)时，两个坐标各自沿lowbit增加方向更新；前缀sum(x,y)时各自沿lowbit减少方向累加。矩形[a,c]×[b,d]用四个前缀按容斥相加减。

正确性说明

二维BIT的每个位置保存对应两个lowbit区间的笛卡尔积和。点增量传播到所有包含该点的块，查询前缀时这些块不重不漏分割矩形前缀。四前缀容斥删除矩形外多余行列并补回重复删除部分，因此输出正好为目标子矩阵和。

复杂度

数组初始化O(nm)，每次更新或询问O(log n log m)，总O(nm+Q log n log m)，空间O(nm)。最大4097²个long long约134MiB，在题目512MiB内；即便无任何操作，矩阵初始化成本也计入。最多30万次增量、每次绝对值10^5，和可超过int，用64位。

易错点

输入按EOF读操作，没有给单独操作次数。第一行是n,m维度，不是n,q。矩形下标从1开始，sum(0,*)为0；增量可以是负数。不要把二维BIT错误写成对x或y只有一层循环。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<long long> bit(size_t(n + 1) * (m + 1));
    auto sum = [&](int x, int y) {
        long long s = 0;
        for (int i = x; i > 0; i -= i & -i)
            for (int j = y; j > 0; j -= j & -j)
                s += bit[size_t(i) * (m + 1) + j];
        return s;
    };
    int op;
    while (cin >> op) {
        if (op == 1) {
            int x, y;
            long long k;
            cin >> x >> y >> k;
            for (int i = x; i <= n; i += i & -i)
                for (int j = y; j <= m; j += j & -j)
                    bit[size_t(i) * (m + 1) + j] += k;
        } else {
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            cout << sum(c, d) - sum(a - 1, d) - sum(c, b - 1) + sum(a - 1, b - 1) << '\n';
        }
    }
}