前缀和 & 差分

前缀和

定义

前缀和可以简单理解为「数列的前 \(n\) 项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。¹

C++ 标准库中实现了前缀和函数 std::partial_sum，定义于头文件 <numeric> 中。

例题

有 \(N\) 个的正整数放到数组 \(A\) 里，现在要求一个新的数组 \(B\)，新数组的第 \(i\) 个数 \(B[i]\) 是原数组 \(A\) 第 \(0\) 到第 \(i\) 个数的和。

输入：

5
1 2 3 4 5

输出：

1	`1 3 6 10 15`

解题思路

递推：B[0] = A[0]，对于 \(i \ge 1\) 则 B[i] = B[i-1] + A[i]。

参考代码

C++Python

#include <iostream>
using namespace std;

int N, A[10000], B[10000];

int main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  // 前缀和数组的第一项和原数组的第一项是相等的。
  B[0] = A[0];

  for (int i = 1; i < N; i++) {
    // 前缀和数组的第 i 项 = 原数组的 0 到 i-1 项的和 + 原数组的第 i 项。
    B[i] = B[i - 1] + A[i];
  }

  for (int i = 0; i < N; i++) {
    cout << B[i] << " ";
  }

  return 0;
}

from itertools import accumulate

input()
print(*accumulate(map(int, input().split())))

二维/多维前缀和

常见的多维前缀和的求解方法有两种。

基于容斥原理

这种方法多用于二维前缀和的情形。给定大小为 \(m\times n\) 的二维数组 \(A\)，要求出其前缀和 \(S\)。那么，\(S\) 同样是大小为 \(m\times n\) 的二维数组，且

\[ S_{i,j} = \sum_{i'\le i}\sum_{j'\le j}A_{i',j'}. \]

类比一维的情形，\(S_{i,j}\) 应该可以基于 \(S_{i-1,j}\) 或 \(S_{i,j-1}\) 计算，从而避免重复计算前面若干项的和。但是，如果直接将 \(S_{i-1,j}\) 和 \(S_{i,j-1}\) 相加，再加上 \(A_{i,j}\)，会导致重复计算 \(S_{i-1,j-1}\) 这一重叠部分的前缀和，所以还需要再将这部分减掉。这就是容斥原理。由此得到如下递推关系：

\[ S_{i,j} = A_{i,j} + S_{i-1,j} + S_{i,j-1} - S_{i-1,j-1}. \]

实现时，直接遍历 \((i,j)\) 求和即可。

示例

考虑一个具体的例子。

二位前缀和示例

这里，\(S\) 是给定矩阵 \(A\) 的前缀和。根据定义，\(S_{3,3}\) 是左图中虚线方框中的子矩阵的和。这里，\(S_{3,2}\) 是蓝色子矩阵的和，\(S_{2,3}\) 是红色子矩阵的和，它们重叠部分的和是 \(S_{2,2}\)。由此可见，如果直接相加 \(S_{3,2}\) 和 \(S_{2,3}\)，会重复计算 \(S_{2,2}\)，所以应该有

\[ S_{3,3} = A_{3,3} + S_{2,3} + S_{3,2} - S_{2,2} = 5 + 18 + 15 - 9 = 29. \]

同样的道理，在已经预处理出二位前缀和后，要查询左上角为 \((i_1,j_1)\)、右下角为 \((i_2,j_2)\) 的子矩阵的和，可以计算

\[ S_{i_2,j_2} - S_{i_1,j_2} - S_{i_2,j_1} + S_{i_1,j_1}. \]

这可以在 \(O(1)\) 时间内完成。

在二维的情形，以上算法的时间复杂度可以简单认为是 \(O(mn)\)，即与给定数组的大小成线性关系。但是，当维度 \(k\) 增大时，由于容斥原理涉及的项数以指数级的速度增长，时间复杂度会成为 \(O(2^kN)\)，这里 \(k\) 是数组维度，而 \(N\) 是给定数组大小。因此，该算法不再适用。

洛谷 P1387 最大正方形

在一个 \(n\times m\) 的只包含 \(0\) 和 \(1\) 的矩阵里找出一个不包含 \(0\) 的最大正方形，输出边长。

参考代码

C++Python

#include <algorithm>
#include <iostream>
using namespace std;
int a[103][103];
int b[103][103];  // 前缀和数组，相当于上文的 sum[]

int main() {
  int n, m;
  cin >> n >> m;

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];
      b[i][j] =
          b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1] + a[i][j];  // 求前缀和
    }
  }

  int ans = 0;

  int l = 1;
  while (l <= min(n, m)) {  // 判断条件
    for (int i = l; i <= n; i++) {
      for (int j = l; j <= m; j++) {
        if (b[i][j] - b[i - l][j] - b[i][j - l] + b[i - l][j - l] == l * l) {
          ans = max(ans, l);  // 在这里统计答案
        }
      }
    }
    l++;
  }

  cout << ans << endl;
  return 0;
}

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [a[0]] + [[i[0]] + [0] * (m - 1) for i in a[1:]]
ans = 0
for i in range(1, n):
    for j in range(1, m):
        if a[i][j]:
            b[i][j] = min(b[i - 1][j], b[i][j - 1], b[i - 1][j - 1]) + 1
            ans = max(ans, b[i][j])
print(ans)

逐维前缀和

对于一般的情形，给定 \(k\) 维数组 \(A\)，大小为 \(N\)，同样要求得其前缀和 \(S\)。这里，

\[ S_{i_1,\cdots,i_k} = \sum_{i'_1\le i_1}\cdots\sum_{i'_k\le i_k} A_{i'_1,\cdots,i'_k}. \]

从上式可以看出，\(k\) 维前缀和就等于 \(k\) 次求和。所以，一个显然的算法是，每次只考虑一个维度，固定所有其它维度，然后求若干个一维前缀和，这样对所有 \(k\) 个维度分别求和之后，得到的就是 \(k\) 维前缀和。

三维前缀和的参考实现

#include <iostream>
#include <vector>

int main() {
  // Input.
  int N1, N2, N3;
  std::cin >> N1 >> N2 >> N3;
  std::vector<std::vector<std::vector<int>>> a(
      N1 + 1, std::vector<std::vector<int>>(N2 + 1, std::vector<int>(N3 + 1)));
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) std::cin >> a[i][j][k];

  // Copy.
  auto ps = a;

  // Prefix-sum for 3rd dimension.
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i][j][k - 1];

  // Prefix-sum for 2nd dimension.
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i][j - 1][k];

  // Prefix-sum for 1st dimension.
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i - 1][j][k];

  // Output.
  for (int i = 1; i <= N1; ++i) {
    for (int j = 1; j <= N2; ++j) {
      for (int k = 1; k <= N3; ++k) {
        std::cout << ps[i][j][k] << ' ';
      }
      std::cout << '\n';
    }
    std::cout << '\n';
  }

  return 0;
}

因为考虑每一个维度的时候，都只遍历了整个数组一遍，这样的算法复杂度是 \(O(kN)\) 的，通常可以接受。

特例：子集和 DP

维度比较大的情形，经常出现在一类叫做 子集和 (SOS, Sum Over Subsets) 的问题中。这是高维前缀和的特例。

问题描述如下。考虑大小为 \(n\) 的集合的全体子集上面定义的函数 \(f\)，现在要求出其子集和函数 \(g\)，它满足

\[ g(S) = \sum_{T\subseteq S}f(T). \]

即 \(g(S)\) 等于其所有子集 \(T\subseteq S\) 上的函数值 \(f(T)\) 的和。

首先，子集和问题可以写成高维前缀和的形式。注意到，子集 \(S\) 可以通过状态压缩的思想表示为长度为 \(n\) 的 0-1 字符串 \(s\)。将字符串的每一位都看作是数组下标的一个维度，那么 \(f\) 其实就是一个 \(n\) 维数组，且每个维度下标都一定在 \(\{0,1\}\) 之间。同时，子集的包含关系就等价于下标的大小关系，即

\[ T\subseteq S \iff \forall i(t_i \le s_i). \]

所以，对子集求和，就是求这个 \(n\) 维数组的前缀和。

现在，可以直接使用前文所述的逐维前缀和的方法求得子集和。时间复杂度是 \(O(n2^n)\)。

参考实现

#include <iostream>
#include <vector>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a(1 << n);
  for (int& x : a) std::cin >> x;

  // Copy.
  auto ps = a;
  // Loop over dimensions.
  for (int i = 0; i < n; ++i) {
    // Loop over i-th dimension.
    for (int st = 0; st < (1 << n); ++st) {
      // This condition implies that i-th dimension is 1.
      if ((st >> i) & 1) {
        // ps[... 1 ...] += ps[... 0 ...]. (i-th dimension)
        ps[st] += ps[st ^ (1 << i)];
      }
    }
  }

  for (int x : ps) std::cout << x << ' ';
  return 0;
}

子集和的逆操作需要通过容斥原理进行。子集和问题也是快速莫比乌斯变换的必要步骤之一。

树上前缀和

设 \(\textit{sum}_i\) 表示结点 \(i\) 到根节点的权值总和。
然后：

若是点权，\(x,y\) 路径上的和为 \(\textit{sum}_x + \textit{sum}_y - \textit{sum}_\textit{lca} - \textit{sum}_{\textit{fa}_\textit{lca}}\)。
若是边权，\(x,y\) 路径上的和为 \(\textit{sum}_x + \textit{sum}_y - 2\cdot\textit{sum}_{lca}\)。

LCA 的求法参见最近公共祖先。

差分

解释

差分是一种和前缀和相对的策略，可以当做是求和的逆运算。

这种策略的定义是令 \(b_i=\begin{cases}a_i-a_{i-1}\,&i \in[2,n] \\ a_1\,&i=1\end{cases}\)

性质

\(a_i\) 的值是 \(b_i\) 的前缀和，即 \(a_n=\sum\limits_{i=1}^nb_i\)
计算 \(a_i\) 的前缀和 \(sum=\sum\limits_{i=1}^na_i=\sum\limits_{i=1}^n\sum\limits_{j=1}^{i}b_j=\sum\limits_{i=1}^n(n-i+1)b_i\)

它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。

示例

譬如使 \([l,r]\) 中的每个数加上一个 \(k\)，即

\[ b_l \leftarrow b_l + k,b_{r + 1} \leftarrow b_{r + 1} - k \]

其中 \(b_l+k=a_l+k-a_{l-1}\)，\(b_{r+1}-k=a_{r+1}-(a_r+k)\)

最后做一遍前缀和就好了。

C++ 标准库中实现了差分函数 std::adjacent_difference，定义于头文件 <numeric> 中。

树上差分

树上差分可以理解为对树上的某一段路径进行差分操作，这里的路径可以类比一维数组的区间进行理解。例如在对树上的一些路径进行频繁操作，并且询问某条边或者某个点在经过操作后的值的时候，就可以运用树上差分思想了。

树上差分通常会结合树基础和最近公共祖先来进行考察。树上差分又分为 点差分 与 边差分，在实现上会稍有不同。

点差分

举例：对树上的一些路径 \(\delta(s_1,t_1), \delta(s_2,t_2), \delta(s_3,t_3)\dots\) 进行访问，问一条路径 \(\delta(s,t)\) 上的点被访问的次数。

对于一次 \(\delta(s,t)\) 的访问，需要找到 \(s\) 与 \(t\) 的公共祖先，然后对这条路径上的点进行访问（点的权值加一），若采用 DFS 算法对每个点进行访问，由于有太多的路径需要访问，时间上承受不了。这里进行差分操作：

\[ \begin{aligned} &d_s\leftarrow d_s+1\\ &d_{lca}\leftarrow d_{\textit{lca}}-1\\ &d_t\leftarrow d_t+1\\ &d_{f(\textit{lca})}\leftarrow d_{f(\textit{lca})}-1\\ \end{aligned} \]

其中 \(f(x)\) 表示 \(x\) 的父亲节点，\(d_i\) 为点权 \(a_i\) 的差分数组。

可以认为公式中的前两条是对蓝色方框内的路径进行操作，后两条是对红色方框内的路径进行操作。不妨令 \(\textit{lca}\) 左侧的直系子节点为 \(\textit{left}\)。那么有 \(d_{\textit{lca}}-1=a_{\textit{lca}}-(a_{\textit{left}}+1)\)，\(d_{f(\textit{lca})}-1=a_{f(\textit{lca})}-(a_{\textit{lca}}+1)\)。可以发现实际上点差分的操作和上文一维数组的差分操作是类似的。

边差分

若是对路径中的边进行访问，就需要采用边差分策略了，使用以下公式：

\[ \begin{aligned} &d_s\leftarrow d_s+1\\ &d_t\leftarrow d_t+1\\ &d_{\textit{lca}}\leftarrow d_{\textit{lca}}-2\\ \end{aligned} \]

由于在边上直接进行差分比较困难，所以将本来应当累加到红色边上的值向下移动到附近的点里，那么操作起来也就方便了。对于公式，有了点差分的理解基础后也不难推导，同样是对两段区间进行差分。

例题

洛谷 3128 最大流

FJ 给他的牛棚的 \(N(2 \le N \le 50,000)\) 个隔间之间安装了 \(N-1\) 根管道，隔间编号从 \(1\) 到 \(N\)。所有隔间都被管道连通了。

FJ 有 \(K(1 \le K \le 100,000)\) 条运输牛奶的路线，第 \(i\) 条路线从隔间 \(s_i\) 运输到隔间 \(t_i\)。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。

解题思路

需要统计每个点经过了多少次，那么就用树上差分将每一次的路径上的点加一，可以很快得到每个点经过的次数。这里采用倍增法计算 LCA，最后对 DFS 遍历整棵树，在回溯时对差分数组求和就能求得答案了。

参考代码

#include <algorithm>
#include <iostream>
using namespace std;

constexpr int MAXN = 50010;

struct node {
  int to, next;
} edge[MAXN << 1];

int fa[MAXN][30], head[MAXN << 1];
int power[MAXN];
int depth[MAXN], lg[MAXN];
int n, k, ans = 0, tot = 0;

void add(int x, int y) {  // 加边
  edge[++tot].to = y;
  edge[tot].next = head[x];
  head[x] = tot;
}

void dfs(int now, int father) {  // dfs求最大压力
  fa[now][0] = father;
  depth[now] = depth[father] + 1;
  for (int i = 1; i <= lg[depth[now]]; ++i)
    fa[now][i] = fa[fa[now][i - 1]][i - 1];
  for (int i = head[now]; i; i = edge[i].next)
    if (edge[i].to != father) dfs(edge[i].to, now);
}

int lca(int x, int y) {  // 求LCA，最近公共祖先
  if (depth[x] < depth[y]) swap(x, y);
  while (depth[x] > depth[y]) x = fa[x][lg[depth[x] - depth[y]] - 1];
  if (x == y) return x;
  for (int k = lg[depth[x]] - 1; k >= 0; k--) {
    if (fa[x][k] != fa[y][k]) x = fa[x][k], y = fa[y][k];
  }
  return fa[x][0];
}

// 用dfs求最大压力，回溯时将子树的权值加上
void get_ans(int u, int father) {
  for (int i = head[u]; i; i = edge[i].next) {
    int to = edge[i].to;
    if (to == father) continue;
    get_ans(to, u);
    power[u] += power[to];
  }
  ans = max(ans, power[u]);
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> k;
  int x, y;
  for (int i = 1; i <= n; i++) {
    lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
  }
  for (int i = 1; i <= n - 1; i++) {  // 建图
    cin >> x >> y;
    add(x, y);
    add(y, x);
  }
  dfs(1, 0);
  int s, t;
  for (int i = 1; i <= k; i++) {
    cin >> s >> t;
    int ancestor = lca(s, t);
    // 树上差分
    power[s]++;
    power[t]++;
    power[ancestor]--;
    power[fa[ancestor][0]]--;
  }
  get_ans(1, 0);
  cout << ans << '\n';
  return 0;
}

习题

前缀和：

二维/多维前缀和：

树上前缀和：

差分：

树上差分：

参考资料与注释

南海区青少年信息学奥林匹克内部训练教材 ↩

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用