前缀和详解及其拓展

前缀和（Prefix Sum） 是一个经典而高效的技巧，常用于快速查询数组区间和、处理计数类问题、解决某些离散数学性质问题。

一维前缀和

一维前缀和是指一个数组中从第一个元素开始，到当前位置的所有元素之和所构成的新数组。

给定一个数组 a，我们定义前缀和数组 s 为：

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

这样一来，任意区间 [l, r] 的区间和就可以通过：

a[l] + a[l+1] + ... + a[r] = s[r] - s[l - 1]

在 \(O(n)\) 的预处理后，区间查询只需 \(O(1)\) 时间。

一维前缀和的经典应用

1.区间和查询

题目描述：

多次询问数组中某段区间的和。

思路：

构建前缀和数组后，区间查询均可在常数时间内完成。

auto query = [&](int l, int r) -> ll
{
    return s[r] - s[l - 1];
};

2.区间和为 0 的子数组个数

题目描述：

统计有多少个子数组，其和为 0。

思路：

设原数组为 a，其前缀和数组为 s。如果某一段区间 [l, r] 的和为 0，根据前缀和的定义有：

\(s[r] – s[l – 1] = 0 \quad \Rightarrow \quad s[r] = s[l – 1]\)

也就是说，如果两个位置的前缀和相同，它们之间的区间和为 0。因此，我们可以枚举右端点 r，在遍历过程中统计当前前缀和出现的次数，只要当前前缀和在之前出现过，就可以与之前所有相同前缀和的位置构成和为 0 的子数组。

具体实现中，使用一个哈希表来记录每个前缀和出现的次数。

unordered_map<ll, int> m;
ll ans = 0;
for (int i = 1; i <= n; ++i)
{
    ++m[s[i - 1]];

    if (m.count(s[i]))
        ans += m[s[i]];
}

最后 ans 中存储的就为最后的答案。

3.区间和为 k 的子数组个数

题目链接：560. 和为 K 的子数组 – 力扣（LeetCode）

题目描述：

统计有多少个子数组，其和为给定整数 k。

思路：

设原数组为 a，前缀和数组为 s。若一段区间 [l, r] 的和为 k，根据前缀和定义有：

\(s[r] – s[l – 1] = k \quad \Rightarrow \quad s[l – 1] = s[r] – k\)

也就是说，只要当前前缀和 s[r] 与之前某个前缀和之差为 k，就说明存在一个区间和为 k 的子数组。我们在遍历过程中用哈希表记录每个前缀和出现的次数。

unordered_map<ll, int> m;
ll ans = 0;
for (int i = 1; i <= n; ++i)
{
    ++m[s[i - 1]];

    if (m.count(s[i] - k))
        ans += m[s[i] - k];
}

最后 ans 即为所求答案。

4.判断区间和是否为 k 的倍数

题目链接：974. 和可被 K 整除的子数组 – 力扣（LeetCode）

题目描述：

给定一个整数数组 a 和一个整数 k，判断是否存在一个非空连续子数组，其元素和是 k 的倍数，即：

\(\sum_{i=l}^{r} a_i \equiv 0 \pmod{k} \quad \text{且} \quad r \ge l\)

思路：

设前缀和数组为 s。若某段子数组 [l, r] 的和是 k 的倍数，有：

\(s[r] – s[l – 1] \equiv 0 \pmod{k} \quad \Rightarrow \quad s[r] \bmod k = s[l – 1] \bmod k\)

这意味着：如果两个不同位置的前缀和模 k 后的余数相同，那么它们之间的子数组和就是 k 的倍数。由于现在要求的是非空子数组，我们只需保证 r ≥ l，即 r - (l-1) ≥ 1 成立。

使用一个哈希表记录每种余数是否出现过，只要在遍历过程中遇到相同余数，即表示存在一个非空子数组，其和是 k 的倍数。

在取模运算中，如果当前前缀和为负数，直接使用 % 运算符可能得到负余数。为保证余数始终为非负数，需使用标准处理方式：

\((x \bmod k + k) \bmod k\)

unordered_map<ll, int> m;
ll ans = 0;
for (int i = 1; i <= n; ++i)
{
    ++m[(s[i - 1] % k + k) % k];

    if (m.count((s[i] % k + k) % k))
        ans += m[(s[i] % k + k) % k];
}

最后 ans 即为所求答案。

二维前缀和

对于一个二维矩阵 a（大小为 \(n \times m\)），我们定义其二维前缀和矩阵 s，其中每个元素 s[i][j] 表示从左上角 (1, 1) 到当前格子 (i, j) 所围成的子矩阵的元素和，即：

\(\sum_{x=1}^{i} \sum_{y=1}^{j} a[x][y]\)

我们可以通过递推公式快速构造前缀和矩阵：

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

其中：

s[i-1][j]：上方区域
s[i][j-1]：左侧区域
s[i-1][j-1]：重复减去的左上角区域（需要加回来）
a[i][j]：当前格子

注意下标从 1 开始，方便处理边界问题。

要查询矩阵中从左上角 \((x_1, y_1)\) 到右下角 \((x_2, y_2)\) 的子矩阵总和，可以使用以下方法：

auto query = [&](int x1, int y1, int x2, int y2) -> ll
{
    return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
};

对应的解释：

\(s[x_2][y_2]\)：目标矩阵从 \((1,1)\) 到 \((x_2,y_2)\)
减去上方 \(s[x_1-1][y_2]\)
减去左侧 \(s[x_2][y_1-1]\)
加回来重复减掉的左上角 \(s[x_1-1][y_1-1]\)

模板链接：304. 二维区域和检索 – 矩阵不可变 – 力扣（LeetCode）

一维差分

差分是一种用于高效处理区间加减操作的技巧。它是前缀和的逆运算，如果前缀和关注的是「累加」，那么差分就是关注「增量」。

给定原数组 a，其差分数组 d 定义为：

\(d[i] = a[i] – a[i – 1] \quad (i \ge 1)\)

如果我们想将区间 [l, r] 所有元素加上一个数 x，只需：

d[l] += x;
d[r + 1] -= x;

最终只需一遍前缀和恢复回原数组：

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

这种方法能将多个区间修改操作从 \(O(n \times q)\) 降为 \(O(n+q)\)。

模板链接：1854. 人口最多的年份 – 力扣（LeetCode）

一维差分的经典应用

1.等差数列差分

等差数列差分就是在数组的一个区间 \([l, r]\) 上，给每个位置按等差数列递增的方式加值，既第 \(l\) 个位置加 \(s\)，第 \(r\) 个位置加 \(e\)，中间是首项为 \(s\)、末项为 \(e\) 的等差数列。

题目链接：https://www.luogu.com.cn/problem/P4231

题目描述：

有 \(N\) 根柱子，初始伤害全为 \(0\)。接着有 \(M\) 次攻击，每次攻击给出 \(l, r, s, e\)：对区间 \([l, r]\) 的柱子施加一个等差伤害，第 \(l\) 根加 \(s\)，第 \(r\) 根加 \(e\)（保证都是整数）。

最后输出所有柱子伤害的异或和与最大值。

数据范围里 \(N\) 可达 \(1e7\)，\(M\) 可达 \(3e5\)，需要线性或近线性做法与 \(O(1)\) 单次修改。

思路：

将给区间加一个等差数列转成对一个二阶差分数组做常数次修改。

因为一次前缀可以将二阶差分还原成一阶差分，再来一次前缀把一阶差分还原成原数组。

而等差数列在区间内是一次函数，其二阶差分是常数，区间外为 \(0\)；因此用二阶差分可以做到 \(O(1)\) 地打标记。

设公差 \(d = (e – s) / (r – l)\)（题目保证这是整数）。

对二阶差分数组 \(b[]\)，一次区间加等差，我们只需要做下面 \(4\) 次点更新：

b[l] += s;
b[l + 1] += d - s;
b[r + 1] += -e - d;
b[r + 2] += e;

完成所有 \(M\) 次更新后：

对 \(b\) 做第一次前缀和，得到一阶差分；
再做第二次前缀和，得到最终伤害数组 \(a[i]\)。

关键代码：

void miyan()
{
    int n, m;
    cin >> n >> m;
    vector<ll> b(n + 3, 0);
    while (m--)
    {
        ll l, r, s, e;
        cin >> l >> r >> s >> e;

        ll d = (e - s) / (r - l);

        b[l] += s;
        b[l + 1] += d - s;
        b[r + 1] += -e - d;
        b[r + 2] += e;
    }

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

    ll ans = 0, maxx = LLONG_MIN;
    for (int i = 1; i <= n; ++i)
    {
        ans ^= b[i];
        maxx = max(maxx, b[i]);
    }

    cout << ans << ' ' << maxx << endl;
}

二维差分

设二维矩阵为 a，差分矩阵为 d，我们对 a 的某个子矩阵 \([x_1,y_1] \sim [x_2,y_2]\) 加上一个数 k，可以通过更新 d 的四个点实现：

\(\begin{aligned} d[x_1][y_1] &+= k \\ d[x_1][y_2 + 1] &-= k \\ d[x_2 + 1][y_1] &-= k \\ d[x_2 + 1][y_2 + 1] &+= k \end{aligned}\)

然后在最后通过二维前缀和还原原始矩阵。

auto insert = [&](int x1, int y1, int x2, int y2, int k)
{
    d[x1][y1] += k;
    d[x2 + 1][y1] -= k;
    d[x1][y2 + 1] -= k;
    d[x2 + 1][y2 + 1] += k;
};

模板链接：P3397 地毯 – 洛谷