前缀和与差分都不复杂，却经常藏在一道题真正的第一步里。

前缀和把一段区间的信息提前累积起来，适合处理大量静态查询；差分只记录相邻位置的变化，适合一次完成大量区间修改。它们看起来方向相反，实际上互为逆运算：对原数组做差分，再求一次前缀和，就能回到原数组。

这一篇从一维前缀和开始，接着整理权值前缀和、二阶前缀和、二维前缀和以及一维、二维差分。正文不依赖配图，重点放在公式、边界和例题中的转换过程。

一维前缀和

给定数组$a_1,a_2,\ldots,a_n$，定义前缀和数组$s$：

$$
s_i=\sum_{j=1}^{i}a_j
$$

规定$s_0=0$，递推式就是：

$$
s_i=s_{i-1}+a_i
$$

因此区间$[l,r]$的和可以拆成“前$r$个数”减去“前$l-1$个数”：

$$
\sum_{i=l}^{r}a_i=s_r-s_{l-1}
$$

预处理代码只有一行：

1
for (int i = 1; i <= n; i++) { cin >> a[i]; s[i] = s[i - 1] + a[i]; }

查询同样只有一行：

1
i64 query(int l, int r) { return s[r] - s[l - 1]; }

建立前缀和需要$O(n)$时间，每次区间查询只需要$O(1)$。额外空间为$O(n)$。

前缀和并不只用于数字求和。只要能把每个位置转成一个贡献值，就可以累积。例如统计字符串中某种相邻字符出现多少次，可以令满足条件的位置贡献$1$，其余位置贡献$0$；统计区间内偶数个数、合法位置数量也是同样的做法。

这里最容易写错的是下标。本文统一使用从$1$开始的闭区间$[l,r]$，因此答案是 s[r]-s[l-1]。如果题目使用从$0$开始的下标或者左闭右开区间，应该先确定前缀数组到底统计了哪些位置，再写减法，不能直接套公式。

权值前缀和与二阶前缀和

权值前缀和

普通前缀和维护$a_i$的累加，权值前缀和则给每个位置乘上一个与下标有关的系数。最常见的定义是：

$$
w_i=\sum_{j=1}^{i}j\cdot a_j
$$

于是区间$[l,r]$的权值和为：

$$
\sum_{i=l}^{r}i\cdot a_i=w_r-w_{l-1}
$$

代码和普通前缀和几乎完全相同：

1
2
3
4
for (int i = 1; i <= n; i++) {
    s[i] = s[i - 1] + a[i];
    w[i] = w[i - 1] + 1LL * i * a[i];
}

为什么会出现$i\cdot a_i$？通常是因为$a_i$在答案中出现了$i$次。

例如把所有以位置$r$结尾的子段全部列出。$a_1$只会出现在$[1,r]$中，$a_2$会出现在$[1,r]$和$[2,r]$中，$a_i$一共出现在$i$个子段里。因此这些子段的总和为：

$$
\sum_{l=1}^{r}\sum_{j=l}^{r}a_j
=\sum_{j=1}^{r}j\cdot a_j
=w_r
$$

更一般地，只要某个位置的贡献系数能够写成关于$i$的一次式，就可以拆成普通前缀和与权值前缀和。例如：

$$
\sum_{i=l}^{r}(x-i+1)a_i
=(x+1)(s_r-s_{l-1})-(w_r-w_{l-1})
$$

这里的$x$在一次查询中是固定值。看到“每个数出现次数不同，而且次数与位置成一次关系”时，就应该想到同时维护$s_i$与$w_i$。

需要注意，权值前缀和与权值树状数组不是同一个概念。前者是给$a_i$乘上下标等系数；后者通常把数值或排名作为下标，维护每个数出现了多少次。

二阶前缀和

如果再对普通前缀和$s$求一次前缀和，得到：

$$
t_i=\sum_{k=1}^{i}s_k
$$

这就是二阶前缀和。展开每个$s_k$：

$$
\begin{aligned}
t_i
&=a_1+(a_1+a_2)+\cdots+(a_1+a_2+\cdots+a_i)\\
&=\sum_{j=1}^{i}(i-j+1)a_j
\end{aligned}
$$

$a_j$从$s_j$开始一直出现在$s_i$中，一共出现$i-j+1$次。继续整理可得：

$$
t_i=(i+1)s_i-w_i
$$

所以二阶前缀和与权值前缀和并不是同一个数组。在普通前缀和$s$已知时，二者可以通过上式互相换算。

如果需要查询$s_l+s_{l+1}+\cdots+s_r$，直接使用：

$$
\sum_{i=l}^{r}s_i=t_r-t_{l-1}
$$

如果要求从$l$开始、分别以$l,l+1,\ldots,r$结尾的所有子段之和，则每一段为$s_i-s_{l-1}$，答案为：

$$
(t_r-t_{l-1})-(r-l+1)s_{l-1}
$$

二阶前缀和也解释了双树状数组中的公式。设$d$是$a$的差分数组，原数组前$x$项的和就是差分前缀和的前缀和：

$$
\sum_{i=1}^{x}a_i
=(x+1)\sum_{i=1}^{x}d_i-\sum_{i=1}^{x}i\cdot d_i
$$

因此区间修改、区间查询需要分别维护$d_i$与$i\cdot d_i$。树状数组只是把这里的静态前缀和换成了可以动态修改的前缀和。

二维前缀和

一维前缀和把区间变成两个前缀之差，二维前缀和做的是同一件事，只是查询对象从线段变成了矩形。

定义$s_{i,j}$表示左上角$(1,1)$到右下角$(i,j)$这个矩形内的元素和。加入$a_{i,j}$时，上方矩形与左侧矩形会重复计算左上部分，所以需要减去一次：

$$
s_{i,j}=a_{i,j}+s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}
$$

查询左上角$(x_1,y_1)$、右下角$(x_2,y_2)$的闭矩形，同样使用容斥：

$$
\begin{aligned}
q={}&s_{x_2,y_2}-s_{x_1-1,y_2}\\
&-s_{x_2,y_1-1}+s_{x_1-1,y_1-1}
\end{aligned}
$$

前两次减法去掉矩形上方和左侧，多减掉的左上角需要补回来。

1
2
3
4
5
6
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        cin >> a[i][j];
        s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    }
}

建立二维前缀和需要$O(nm)$时间，每次矩形查询为$O(1)$，额外空间为$O(nm)$。

二维前缀和仍然依赖第$0$行和第$0$列作为空边界。数组至少要开到$(n+1)\times(m+1)$，并保证这些边界初始为$0$。如果原坐标可能从$0$开始，可以整体向右下平移一格，避免在每次查询时特判负下标。

差分

一维差分

定义差分数组$d$：

$$
d_i=a_i-a_{i-1}
$$

规定$a_0=0$，那么对$d$求前缀和就能还原$a$：

$$
a_i=\sum_{j=1}^{i}d_j
$$

如果要让区间$[l,r]$中的每个数增加$k$，区间内部相邻两项都增加了$k$，它们之间的差没有变化。真正需要修改的只有两个边界：

$$
d_l\gets d_l+k
$$

$$
d_{r+1}\gets d_{r+1}-k
$$

完成全部修改以后，求一次前缀和即可得到最终数组：

1
for (int i = 1; i <= n; i++) a[i] = a[i - 1] + d[i];

每次区间修改只需要$O(1)$，最后还原数组需要$O(n)$。

普通差分更适合“先完成全部区间修改，最后统一输出或处理”的离线场景。如果修改与查询交错出现，尚未还原的差分数组不能直接回答任意区间查询，此时通常需要树状数组或线段树。

二维差分

二维差分把“矩形整体增加”转换成四个角的修改。

让闭矩形$(x_1,y_1)$到$(x_2,y_2)$全部增加$k$：

$$
\begin{aligned}
d_{x_1,y_1}&\gets d_{x_1,y_1}+k\\
d_{x_2+1,y_1}&\gets d_{x_2+1,y_1}-k\\
d_{x_1,y_2+1}&\gets d_{x_1,y_2+1}-k\\
d_{x_2+1,y_2+1}&\gets d_{x_2+1,y_2+1}+k
\end{aligned}
$$

前两个位置控制竖直方向的开始与结束，后两个位置再处理水平方向。所有修改完成以后，对$d$求二维前缀和：

$$
d_{i,j}\gets d_{i,j}+d_{i-1,j}+d_{i,j-1}-d_{i-1,j-1}
$$

此时$d_{i,j}$就是位置$(i,j)$最终增加的总量。

一维与二维的关系可以简单整理为：

维度 前缀和擅长的操作 差分擅长的操作 还原方式
一维 静态区间查询 区间修改 一次前缀和
二维 静态矩形查询 矩形修改 二维前缀和

例题与典型应用

下面七道题按照使用方式排列。前四道先把基础模型写熟，后三道再处理二维修改、贡献次数和连续累加。

题目 核心方法 需要注意的地方
洛谷 P8218 求区间和 一维前缀和 使用 i64 保存答案
AtCoder ABC122 C GeT AC 贡献前缀和 相邻字符的右端点范围
洛谷 P2280 激光炸弹 二维前缀和 坐标整体平移一格
AtCoder ABC035 C オセロ 一维差分 翻转次数只看奇偶性
洛谷 P3397 地毯 二维差分 四个角的正负号
Codeforces 276C Maximum Sum 差分与贪心 价值和使用次数同序配对
Codeforces 1355C Count Triangles 差分与两次前缀和 统计和大于$z$的数对

例题一：洛谷 P8218 求区间和

题目链接：洛谷 P8218 求区间和

给定长度为$n$的正整数序列和$m$个区间，分别求每个闭区间$[l,r]$的元素和。

这是前缀和最直接的使用方式。先建立$s_i$，每次输出$s_r-s_{l-1}$即可。

虽然单个$a_i$不大，但是区间和可能超过 int。把前缀和数组声明为 i64 更稳妥。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

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

    int n;
    cin >> n;
    vector<i64> s(n + 1);
    for (int i = 1; i <= n; i++) { i64 x; cin >> x; s[i] = s[i - 1] + x; }
    int m;
    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << '\n';
    }
    return 0;
}

预处理时间为$O(n)$，每次查询为$O(1)$，空间复杂度为$O(n)$。

例题二：AtCoder ABC122 C GeT AC

题目链接：AtCoder ABC122 C GeT AC

给定一个只含 A、C、G、T 的字符串。每次询问子串$[l,r]$中有多少个连续的 AC。

令$c_i$表示位置$i-1$和$i$是否组成 AC：成立时为$1$，否则为$0$。再对$c$建立前缀和$s$。

一个完全位于$[l,r]$中的 AC，右端点只能位于$[l+1,r]$。如果$s_i$统计右端点不超过$i$的数量，答案就是：

$$
s_r-s_l
$$

这里减去的是$s_l$而不是$s_{l-1}$。因为右端点恰好为$l$的 AC 会跨出查询区间左边界，同样不能计入。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

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

    int n, q;
    string str;
    cin >> n >> q >> str;
    str = " " + str;
    vector<int> s(n + 1);
    for (int i = 2; i <= n; i++) s[i] = s[i - 1] + (str[i - 1] == 'A' && str[i] == 'C');
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l] << '\n';
    }
    return 0;
}

预处理时间为$O(n)$，每次查询为$O(1)$，空间复杂度为$O(n)$。

例题三：洛谷 P2280 激光炸弹

题目链接：洛谷 P2280 激光炸弹

平面上有若干目标，每个目标具有一定价值。选择一个边长固定、边与坐标轴平行的正方形，求内部目标的最大价值和。同一坐标可能出现多个目标。

坐标范围不超过$5000$，可以直接建立二维网格。先把同一坐标的价值累加，再求二维前缀和，最后枚举每个边长为$k$的正方形。

原坐标可能等于$0$。为了保留第$0$行和第$0$列作为空边界，读入时把$x,y$都增加$1$：

1
s[x + 1][y + 1] += v;

枚举正方形右下角$(i,j)$时，覆盖的网格范围为$(i-k,i]\times(j-k,j]$，价值和为：

$$
s_{i,j}-s_{i-k,j}-s_{i,j-k}+s_{i-k,j-k}
$$

点击展开完整代码
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
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

constexpr int V = 5001;
int s[V + 2][V + 2];

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

    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int x, y, v;
        cin >> x >> y >> v;
        s[x + 1][y + 1] += v;
    }
    for (int i = 1; i <= V; i++)
        for (int j = 1; j <= V; j++)
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    int ans = 0;
    for (int i = k; i <= V; i++) {
        for (int j = k; j <= V; j++) {
            int cur = s[i][j] - s[i - k][j] - s[i][j - k] + s[i - k][j - k];
            ans = max(ans, cur);
        }
    }
    cout << ans << '\n';
    return 0;
}

设坐标边界为$V$，时间复杂度为$O(V^2)$，空间复杂度为$O(V^2)$。这里$V=5001$，全局数组大约占用$100$ MB，不能放在函数栈中。

例题四：AtCoder ABC035 C オセロ

题目链接：AtCoder ABC035 C オセロ

有$n$枚初始均为$0$的棋子。每次把区间$[l,r]$内的棋子全部翻转，完成$q$次操作后输出最终的$01$串。

一次翻转相当于让区间内每个位置的翻转次数增加$1$。使用差分数组记录：

1
2
d[l]++;
d[r + 1]--;

最后求前缀和，得到每个位置一共被翻转了多少次。偶数次仍然为$0$，奇数次变成$1$，因此只需要输出 d[i]&1。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

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

    int n, q;
    cin >> n >> q;
    vector<int> d(n + 2);
    while (q--) {
        int l, r;
        cin >> l >> r;
        d[l]++;
        d[r + 1]--;
    }
    for (int i = 1; i <= n; i++) { d[i] += d[i - 1]; cout << (d[i] & 1); }
    cout << '\n';
    return 0;
}

总时间复杂度为$O(n+q)$，空间复杂度为$O(n)$。

例题五：洛谷 P3397 地毯

题目链接：洛谷 P3397 地毯

在$n\times n$的格子上依次铺设$m$张矩形地毯，输出每个格子最终被覆盖了多少次。

如果对每张地毯内部的所有格子逐一增加$1$，最坏复杂度会达到$O(mn^2)$。二维差分只修改四个角，每张地毯可以在$O(1)$时间内记录。

对于左上角$(x_1,y_1)$、右下角$(x_2,y_2)$的闭矩形：

1
2
3
4
d[x1][y1]++;
d[x2 + 1][y1]--;
d[x1][y2 + 1]--;
d[x2 + 1][y2 + 1]++;

全部地毯处理完成以后，求一次二维前缀和，当前值就是该格子的覆盖次数。

点击展开完整代码
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
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

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

    int n, m;
    cin >> n >> m;
    vector<vector<int>> d(n + 2, vector<int>(n + 2));
    while (m--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        d[x1][y1]++;
        d[x2 + 1][y1]--;
        d[x1][y2 + 1]--;
        d[x2 + 1][y2 + 1]++;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
            cout << d[i][j] << " \n"[j == n];
        }
    }
    return 0;
}

总时间复杂度为$O(m+n^2)$，空间复杂度为$O(n^2)$。

例题六：Codeforces 276C Little Girl and Maximum Sum

题目链接：Codeforces 276C Little Girl and Maximum Sum

给定一个数组和$q$个区间。可以在回答询问以前任意重排数组，要求所有区间和的总和最大。

与其逐个计算区间，不如先统计每个位置一共会被询问多少次。设位置$i$被覆盖$c_i$次，那么所有询问答案之和就是：

$$
\sum_{i=1}^{n}a_i c_i
$$

每个询问$[l,r]$都让$c_l,c_{l+1},\ldots,c_r$增加$1$，正好可以使用差分数组在$O(1)$时间记录。

接下来需要决定如何重排$a$。为了让乘积和最大，应当把最大的$a_i$放在使用次数最多的位置，第二大的放在第二多的位置。因此分别排序$a$与$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
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

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

    int n, q;
    cin >> n >> q;
    vector<i64> a(n), d(n + 2);
    for (i64 &x : a) cin >> x;
    while (q--) {
        int l, r;
        cin >> l >> r;
        d[l]++;
        d[r + 1]--;
    }
    for (int i = 1; i <= n; i++) d[i] += d[i - 1];
    sort(a.begin(), a.end());
    sort(d.begin() + 1, d.begin() + n + 1);

    i64 ans = 0;
    for (int i = 1; i <= n; i++) ans += a[i - 1] * d[i];
    cout << ans << '\n';
    return 0;
}

统计覆盖次数需要$O(n+q)$，排序需要$O(n\log n)$，总时间复杂度为$O(n\log n+q)$，空间复杂度为$O(n)$。

例题七：Codeforces 1355C Count Triangles

题目链接：Codeforces 1355C Count Triangles

给定$a\le b\le c\le d$，统计满足下面范围的非退化三角形数量：

$$
a\le x\le b\le y\le c\le z\le d
$$

由于$x\le y\le z$已经由取值范围保证，三角形不等式中只需要检查：

$$
x+y>z
$$

固定$x$以后，$y$在$[b,c]$内变化，和$s=x+y$会依次取遍区间$[x+b,x+c]$，每个值恰好对应一个$(x,y)$。

建立数组$cnt$，让$cnt_s$表示有多少对$(x,y)$满足$x+y=s$。对于每个$x$，不必枚举所有$y$，只要对$[x+b,x+c]$整体增加$1$：

1
2
cnt[x + b]++;
cnt[x + c + 1]--;

第一次求前缀和以后，$cnt_s$变成和恰好等于$s$的数对数量。再求一次前缀和，$cnt_s$就变成和不超过$s$的数对数量。

记全部$(x,y)$的数量为$total$。对于固定的$z$，合法数对数量就是：

$$
total-cnt_z
$$

这道题中的“两次前缀和”有不同职责：第一次还原差分，第二次累计答案。写代码时最好先说清楚数组在每一步表示什么，否则很容易多做或少做一次累加。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

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

    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int lim = max(b + c, d) + 2;
    vector<i64> cnt(lim + 1);
    for (int x = a; x <= b; x++) { cnt[x + b]++; cnt[x + c + 1]--; }
    for (int i = 1; i <= lim; i++) cnt[i] += cnt[i - 1];
    for (int i = 1; i <= lim; i++) cnt[i] += cnt[i - 1];

    i64 total = cnt[lim], ans = 0;
    for (int z = c; z <= d; z++) ans += total - cnt[z];
    cout << ans << '\n';
    return 0;
}

令$V=\max(b+c,d)$，数组长度、时间复杂度和空间复杂度均为$O(V)$。

总结与常见问题

应该使用哪一种？

  • 数组不再修改，需要大量区间查询：使用前缀和；
  • 每个位置的贡献次数与下标有关：考虑普通前缀和与权值前缀和；
  • 需要查询若干段前缀和的总和：建立二阶前缀和；
  • 静态矩形查询：使用二维前缀和；
  • 先完成大量区间修改，最后统一得到数组：使用差分；
  • 先完成大量矩形修改，最后统一得到网格：使用二维差分；
  • 修改和查询在线交错出现：继续考虑树状数组或线段树。

常见错误

1. 忘记预留第$0$项

前缀和查询需要访问$s_{l-1}$。当$l=1$时会访问$s_0$，因此数组必须多开一格，并让$s_0=0$。

2. 使用 int 保存区间和

即使每个$a_i$都能放进 int，$n$个数相加、位置权值$i\cdot a_i$以及答案中的乘积仍然可能溢出。涉及累加值时优先检查是否需要 i64。

3. 差分的右端点少加$1$

闭区间$[l,r]$增加$k$，结束位置是$r+1$：

1
2
d[l] += k;
d[r + 1] -= k;

如果把结束位置误写成$r$，位置$r$本身就不会得到这次修改。

4. 二维容斥的符号写反

无论二维前缀查询还是二维差分修改，都可以先从一维思考：一个方向开始、一个方向结束。不要只背四个位置，先确定每个位置影响的是哪一块区域。

5. 把普通差分当成在线数据结构

差分数组能够快速记录修改，但在重新求前缀和以前，$d_i$并不是$a_i$。修改后立刻查询任意区间时，普通差分通常不够用。

6. 不清楚连续两次前缀和的含义

第一次前缀和可能是在还原差分，第二次才是在统计累计数量。每做一次累加，都应当重新写清楚数组当前保存的内容。

复杂度分析

方法 预处理或还原 单次操作 空间复杂度
一维前缀和 $O(n)$ 区间查询$O(1)$ $O(n)$
权值或二阶前缀和 $O(n)$ 区间查询$O(1)$ $O(n)$
二维前缀和 $O(nm)$ 矩形查询$O(1)$ $O(nm)$
一维差分 还原$O(n)$ 区间修改$O(1)$ $O(n)$
二维差分 还原$O(nm)$ 矩形修改$O(1)$ $O(nm)$