跳转至

前缀和 & 差分

前缀和

前缀和是一种较为简单的算法,可以大大减少时间复杂度。我们可以简单理解为“数列的前 n 项的和”。下面我们用一个例题来了解一下前缀和的主要思路。

例题

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

对于这道题,我们有两种做法:

  • 把对数组 A 的累加依次放入数组 B 中。
  • 递推: B[i] = B[i-1] + A[i] ,前提 B[0] = A[0]

参考程序:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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++) {
    B[i] = B[i - 1] + A[i];
  }

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

  return 0;
}

输入:

1
2
5
1 2 3 4 5

输出:

1
1 3 6 10 15

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

B[i] = B[i-1] + A[i] 相信大家也能理解这个式子。意思就是:前缀和数组的第 i 项等于数组 A 的 0 到 i-1 项的和加数组 A 的第 i 项。

习题

  1. 洛谷 U53525 前缀和(例题)

参考

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

二维/多维前缀和

其实前缀和几乎都是基于容斥原理,所以各种拓展自己手推一下就行了。
这里用二维前缀和为例讲解一下前缀和扩展到多维的方式。

比如我们有这样一个矩阵 a,可以视为二维数组:

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

我们定义一个矩阵 sumsum_{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

第一个问题就是递推求 sum的过程, sum_{i,j} = sum_{i - 1,j} + sum_{i,j - 1} - sum_{i - 1,j - 1} + a_{i,j}
因为加了 sum_{i - 1,j}sum_{i,j - 1}重复了 sum_{i - 1,j - 1},所以减去。

第二个问题就是如何应用,譬如求 (x1,y1) - (x2,y2)子矩阵的和。
那么,根据类似的思考过程,易得答案为 sum_{x2,y2} - sum_{x1 - 1,y2} - sum_{x2,y1 - 1} + sum_{x1 - 1,y1 - 1}

习题

  1. CodeVS 1373. 射命丸文

树上前缀和

sum_i表示结点 i到根节点的权值总和。
然后若是点权, x,y路径上的和为 sum_x + sum_y - sum_{lca} - sum_{fa_{lca}}
否则若是边权, x,y路径上的和为 sum_x + sum_y - 2sum_{lca}

至于 lca 的求法请移步最近公共祖先

习题

  1. LOJ 10134.Dis
  2. LOJ 2491. 求和

差分

差分,是一种和前缀和相对的策略。
这种策略是,令 b_i = a_i - a_{i - 1},即相邻两数的差。
易得对这个序列做一遍前缀和就得到了原来的 a序列。

它可以维护多次对序列的一个区间加上一个数,并在最后询问某一位的数或是多次询问某一位的数。(总之修改操作一定要在查询操作之前)
具体怎么搞?譬如使 [l,r]每个数加上一个 k,就是 b_l \leftarrow b_l + k,b_{r + 1} \leftarrow b_{r + 1} - k
最后做一遍前缀和就好了。

对于多维差分,自己手推一下就好了。(逃

习题

待补充。

树上差分

我以前一直以为树上差分也是树上前缀和相对的策略,但是不知道怎么搞。

后来发现还是有点区别的。

至少人家是基于子树和而非到根的和。

如果使 x,y路径上的点权增加 kb_x \leftarrow b_x + k,b_y \leftarrow b_y + k,b_{lca} \leftarrow b_{lca} - k,b_{fa_{lca}} \leftarrow b_{fa_{lca}} - k, 如果是边权, b_x \leftarrow b_x + k,b_y \leftarrow b_y + k,b_{lca} \leftarrow b_{lca} - 2k

然后一遍搜索求一下子树和答案就出来了。

习题

  1. 洛谷 3128. 最大流

评论