跳转至

前缀和 & 差分

前缀和

前缀和是一种较为简单的算法，可以大大减少时间复杂度。我们可以简单理解为“数列的前 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 项。

习题

参考

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

二维/多维前缀和

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

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

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

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

第一个问题就是递推求 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}。

习题

树上前缀和

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

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

习题

差分

差分，是一种和前缀和相对的策略。
这种策略是，令 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路径上的点权增加 k， b_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。

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

习题

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

评论