跳转至

前綴和 & 差分

前綴和

定義

前綴和可以簡單理解為「數列的前 \(n\) 項的和」，是一種重要的預處理方式，能大大降低查詢的時間複雜度。1

C++ 標準庫中實現了前綴和函數 std::partial_sum，定義於頭文件 <numeric> 中。

例題

例題

有 \(N\) 個的正整數放到數組 \(A\) 裏，現在要求一個新的數組 \(B\)，新數組的第 \(i\) 個數 \(B[i]\) 是原數組 \(A\) 第 \(0\) 到第 \(i\) 個數的和。

輸入：

1
2
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]。

參考代碼 
 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
#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;
}

1
2
3
from itertools import accumulate
input()
print(*accumulate(map(int, input().split())))

二維/多維前綴和

多維前綴和的普通求解方法幾乎都是基於容斥原理。

示例：一維前綴和擴展到二維前綴和

比如我們有這樣一個矩陣 \(a\)，可以視為二維數組：

1
2
3
1 2 4 3
5 1 2 4
6 3 5 9

我們定義一個矩陣 \(\textit{sum}\) 使得 \(\textit{sum}_{x,y} = \sum\limits_{i=1}^x \sum\limits_{j=1}^y a_{i,j}\)，
那麼這個矩陣長這樣：

1
2
3
1  3  7  10
6  9  15 22
12 18 29 45

第一個問題就是遞推求 \(\textit{sum}\) 的過程，\(\textit{sum}_{i,j} = \textit{sum}_{i - 1,j} + \textit{sum}_{i,j - 1} - \textit{sum}_{i - 1,j - 1} + a_{i,j}\)。

因為同時加了 \(\textit{sum}_{i - 1,j}\) 和 \(\textit{sum}_{i,j - 1}\)，故重複了 \(\textit{sum}_{i - 1,j - 1}\)，減去。

第二個問題就是如何應用，譬如求 \((x_1,y_1) - (x_2,y_2)\) 子矩陣的和。

那麼，根據類似的思考過程，易得答案為 \(\textit{sum}_{x_2,y_2} - \textit{sum}_{x_1 - 1,y_2} - sum_{x_2,y_1 - 1} + sum_{x_1 - 1,y_1 - 1}\)。

例題

洛谷 P1387 最大正方形

在一個 \(n\times m\) 的只包含 \(0\) 和 \(1\) 的矩陣裏找出一個不包含 \(0\) 的最大正方形，輸出邊長。

參考代碼 
 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
#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 = 1;

  int l = 2;
  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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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)

基於 DP 計算高維前綴和

基於容斥原理來計算高維前綴和的方法，其優點在於形式較為簡單，無需特別記憶，但當維數升高時，其複雜度較高。這裏介紹一種基於 DP 計算高維前綴和的方法。該方法即通常語境中所稱的 高維前綴和。

設高維空間 \(U\) 共有 \(D\) 維，需要對 \(f[\cdot]\) 求高維前綴和 \(\text{sum}[\cdot]\)。令 \(\text{sum}[i][\text{state}]\) 表示同 \(\text{state}\) 後 \(D - i\) 維相同的所有點對於 \(\text{state}\) 點高維前綴和的貢獻。由定義可知 \(\text{sum}[0][\text{state}] = f[\text{state}]\)，以及 \(\text{sum}[\text{state}] = \text{sum}[D][\text{state}]\)。

其遞推關係為 \(\text{sum}[i][\text{state}] = \text{sum}[i - 1][\text{state}] + \text{sum}[i][\text{state}']\)，其中 \(\text{state}'\) 為第 \(i\) 維恰好比 \(\text{state}\) 少 \(1\) 的點。該方法的複雜度為 \(O(D \times |U|)\)，其中 \(|U|\) 為高維空間 \(U\) 的大小。

一種實現的偽代碼如下：

\[ \begin{array}{ll} \textbf{for } state \\ \qquad sum[state] \gets f[state] \\ \textbf{for } i \gets 0 \textbf{ to } D \\ \qquad \textbf{for } state' \textbf{ in } \text{lexicographical order} \\ \qquad \qquad sum[state] \gets sum[state] + sum[state'] \end{array} \]

樹上前綴和

設 \(\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}^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 遍歷整棵樹，在回溯時對差分數組求和就能求得答案了。

參考代碼 
 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
71
72
73
74
75
76
#include <bits/stdc++.h>

using namespace std;
#define 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() {
  scanf("%d %d", &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++) {  // 建图
    scanf("%d %d", &x, &y);
    add(x, y);
    add(y, x);
  }
  dfs(1, 0);
  int s, t;
  for (int i = 1; i <= k; i++) {
    scanf("%d %d", &s, &t);
    int ancestor = lca(s, t);
    // 树上差分
    power[s]++;
    power[t]++;
    power[ancestor]--;
    power[fa[ancestor][0]]--;
  }
  get_ans(1, 0);
  printf("%d\n", ans);
  return 0;
}

習題

前綴和：

二維/多維前綴和：

基於 DP 計算高維前綴和：

樹上前綴和：

差分：

樹上差分：

參考資料與註釋

  1. 南海區青少年信息學奧林匹克內部訓練教材 ↩

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