形式化题目

维护一个大小为 $n \times m$ 的矩阵 $A$（下标从 $1$ 开始），初始全为 $0$。支持如下两类在线操作：

1. 单点增加：给定 $x, y, k$，执行 $A_{x,y} \leftarrow A_{x,y} + k$。
2. 子矩形求和：给定 $a, b, c, d$（保证 $1 \le a \le c \le n$ 且 $1 \le b \le d \le m$），计算并返回 $\sum_{i=a}^{c} \sum_{j=b}^{d} A_{i,j}$。

正解：二维树状数组

思路

1. 朴素做法及其局限

若直接用二维数组维护原矩阵，单点增加操作时间复杂度为 $O(1)$。但对于每次矩形求和操作，需要遍历所有属于行范围 $[a, c]$ 与列范围 $[b, d]$ 的元素，单次查询时间复杂度为 $O((c - a + 1)(d - b + 1)) = O(nm)$。在 $n, m \le 4096$ 且操作数达到 $3 \times 10^5$ 的规模下，总体时间复杂度将达到 $O(q \cdot nm)$，显然会超时。

若采用静态二维前缀和，单次查询为 $O(1)$，但每次单点修改需要更新后续所有前缀和，单次修改耗时 $O(nm)$，同样无法承受。

2. 二维前缀和与容斥原理

定义二维前缀和 $S(x, y) = \sum_{i=1}^{x} \sum_{j=1}^{y} A_{i,j}$。对于任意查询矩形 $[a, c] \times [b, d]$，根据容斥原理，该区域内的元素和可以表示为 4 个前缀矩形和的线性组合：

因此，只要我们能高效地支持：

1. 单点修改 $A_{x,y}$；
2. 动态查询任意前缀和 $S(x, y)$。

就可以在相同的时间复杂度内完成子矩形查询。

3. 二维树状数组（2D Fenwick Tree）

一维树状数组通过管辖区间 $[i - \text{lowbit}(i) + 1, i]$ 实现动态前缀和与单点加，单次操作复杂度为 $O(\log n)$。

将一维树状数组推广到二维：外层树状数组维护行坐标，每个行节点内部嵌套一个一维树状数组维护列坐标。节点 $(i, j)$ 管辖的原矩阵区域为：

• 单点更新 add(x, y, k)：从外层 $i = x$ 开始，每次 $i \leftarrow i + \text{lowbit}(i)$；对于每个合法的行下标 $i$，内层从 $j = y$ 开始，每次 $j \leftarrow j + \text{lowbit}(j)$，将树状数组节点对应的值加上 $k$。
• 前缀查询 query(x, y)：从外层 $i = x$ 开始，每次 $i \leftarrow i - \text{lowbit}(i)$；内层从 $j = y$ 开始，每次 $j \leftarrow j - \text{lowbit}(j)$，累加所有管辖区间的和。

对于 Python 实现，若直接开辟 $(n + 1) \times (m + 1)$ 的定长二维数组，当 $n, m = 4096$ 时需要分配约 $1.6 \times 10^7$ 个元素，空间占用大且分配慢；使用 list[dict[int, int]] 稀疏存储只对被修改的位置分配内存，既省内存又利于快速初始化。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 17:08
# update_at: 2026-09-30 17:08

import sys


def add(tree: list[dict[int, int]], x: int, y: int, k: int, n: int, m: int) -> None:
    """在二维树状数组中将位置 (x, y) 处的值增加 k。"""
    i = x
    while i <= n:
        row = tree[i]
        j = y
        while j <= m:
            row[j] = row.get(j, 0) + k
            j += j & -j
        i += i & -i


def query(tree: list[dict[int, int]], x: int, y: int) -> int:
    """查询左上角 (1, 1) 到 (x, y) 的前缀矩形元素和。"""
    res = 0
    i = x
    while i > 0:
        row = tree[i]
        j = y
        while j > 0:
            res += row.get(j, 0)
            j -= j & -j
        i -= i & -i
    return res


def query_rect(tree: list[dict[int, int]], a: int, b: int, c: int, d: int) -> int:
    """利用二维前缀和容斥原理求子矩阵 [a, c] x [b, d] 内的元素和。"""
    return (
        query(tree, c, d)
        - query(tree, a - 1, d)
        - query(tree, c, b - 1)
        + query(tree, a - 1, b - 1)
    )


def solve() -> None:
    tokens = sys.stdin.buffer.read().split()
    if not tokens:
        return
    it = map(int, tokens)
    n = next(it)
    m = next(it)

    tree: list[dict[int, int]] = [{} for _ in range(n + 1)]
    out: list[str] = []

    for op in it:
        if op == 1:
            x, y, k = next(it), next(it), next(it)
            add(tree, x, y, k, n, m)
        else:
            a, b, c, d = next(it), next(it), next(it), next(it)
            out.append(str(query_rect(tree, a, b, c, d)))

    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:12
 * update_at: 2026-10-05 07:12
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 4097; // 坐标最大到 4096，数组下标要多开一位

ll n, m;
ll tree[MAXN][MAXN]; // tree[i][j] 管辖原矩阵 [i-lowbit(i)+1, i] * [j-lowbit(j)+1, j] 的矩形和

// 单点增加：把 A[x][y] 加上 k，沿两个方向的 lowbit 链向上更新所有管辖它的节点。
void add(ll x, ll y, ll k) {
    for (ll i = x; i <= n; i += i & -i) {
        for (ll j = y; j <= m; j += j & -j) {
            tree[i][j] += k;
        }
    }
}

// 二维前缀和查询：返回 A[1..x][1..y] 的元素和，沿两个方向的 lowbit 链向下累加。
ll query(ll x, ll y) {
    ll res = 0;
    for (ll i = x; i > 0; i -= i & -i) {
        for (ll j = y; j > 0; j -= j & -j) {
            res += tree[i][j];
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    ll op;
    while (cin >> op) {
        if (op == 1) {
            ll x, y, k;
            cin >> x >> y >> k;
            add(x, y, k);
        } else {
            ll a, b, c, d;
            cin >> a >> b >> c >> d;
            // 容斥：子矩阵 [a, c] * [b, d] 的和 = 四个前缀矩形和的加减组合
            ll ans = query(c, d) - query(a - 1, d) - query(c, b - 1) + query(a - 1, b - 1);
            cout << ans << "\n";
        }
    }

    return 0;
}

复杂度

• 时间复杂度：
  • 单点增加：外层循环执行 $O(\log n)$ 次，内层循环执行 $O(\log m)$ 次，单次修改耗时 $O(\log n \log m)$。
  • 矩形查询：执行 4 次二维前缀查询，每次前缀查询耗时 $O(\log n \log m)$，单次查询耗时 $O(\log n \log m)$。
  • 总时间复杂度为 $O(q \log n \log m)$。在 $q = 3 \times 10^5$、$n, m \le 4096$ 下，$\log_2 n, \log_2 m \le 12$，总操作量约 $3 \times 10^5 \times 144 \approx 4.3 \times 10^7$ 次基本运算，完全满足时限要求。
• 空间复杂度：
  • 二维树状数组每个修改操作最多增加 $O(\log n \log m)$ 个字典键值对。
  • 最多 $q$ 次修改，字典总大小不超过 $O(q \log n \log m)$；外层列表大小为 $O(n)$。总空间复杂度为 $O(n + q \log n \log m)$，满足内存限制。

图示解析

二维子矩阵和通过二维前缀和容斥计算的示意图如下：

flowchart TD
    subgraph 全集与子集划分
        A["S(c, d): 包含区域 [1, c] × [1, d]"]
        B["减去上方: - S(a - 1, d)"]
        C["减去左方: - S(c, b - 1)"]
        D["补回重复减去的左上方: + S(a - 1, b - 1)"]
    end
    A --> B --> C --> D
    D --> Res["目标矩形 [a, c] × [b, d] 的权值和"]

矩阵网格划分示意图：

每个树状数组节点维护一个二维矩形区间的和，沿 lowbit 链式向上更新与向下累加，实现了二维维度上的动态树形维护。

总结

1. 本题是经典的二维单点修改、二维子矩阵和查询模板题。
2. 核心数学思想是将二维矩形求和通过容斥原理转化为 4 次二维前缀矩形求和。
3. 动态维护二维前缀和利用二维树状数组，将两个维度独立做树状数组分解，每次修改和查询只需 $O(\log n \log m)$ 时间。
4. 在 Python 实现中，结合稀疏字典表示每行的内层树状数组，可以避免开辟大规格全量数组的内存和初始化开销。