Data Structure 10 - Summation Sequence and Difference Sequence
# 前置知识
在阅读本文档前,请确保你已经掌握线性表的基础知识,详见 Data Structure 知识板块中的 01 - Linear List 文档。
# 前言
前缀和序列 与 差分序列 是两种基础数据结构,多数情况下会用顺序表来实现,常用于解决简单区间问题。
前缀和序列与差分序列包含了最基础的数据结构思想,它们的优点是简单易于实现,缺点是局限性大。它们通常无法解决复杂区间问题,但能够以最优效率解决一些简单区间问题。它们很少单独成题,通常是解决题目所需的辅助手段,甚至以变体出现,因此关键是理解两者的作用和思想,并灵活使用,甚至于解决各类与之思想相似的变种问题,而非生搬硬套模板。
为便于理解它们存在的意义,两者各自通过一个经典问题来引入。参考了ddd大佬的课件。
# 前缀和序列
# 问题引入
我们考虑如下的算法问题:
给定一个长为 的数组 ,下标为 ,有 次操作,每次给定一个二元组 ,求 的值。
直接根据题意求解的时间复杂度为 ,是个人都会做。但是当 的值比较大的时候,例如 , 时,就不行了。此时我们引入前缀和序列来解决问题。
# 定义
设 表示数组中前 个数的和,即 。称这个 序列为 前缀和序列 。
容易发现 ,也就是说,在给定序列 的情况下,我们可以在 时间内利用简单递推求出前缀和序列:
sum[0] = 0;
for (int i = 1; i <= n; i ++) {
sum[i] = sum[i-1] + a[i];
}
# 问题解决
容易发现, ,即 。也就是说,如果我们预先求出前缀和数组,就可以 地解决每个查询,那么总的时间复杂度为 。
inline int query(int l, int r) {
return (sum[r] - sum[l-1]);
}
# 应用
前缀和序列可用于解决不带修改的区间求和问题。注意这里强调了不带修改,这指的是 中元素的值不会改变,或很少被改变。如果问题中存在频繁修改,那么前缀和通常难以胜任。
# 差分序列
# 问题引入
我们考虑如下的算法问题:
给定一个长为 的数组 ,下标为 ,有 次操作,每次给定一个二元组 和一个整数 ,表示令区间 内的所有元素 。输出完成所有操作后的数组 。
类似于前缀和问题, 的方法是个人都会,但是当 , 时就不行了,但是这里你显然没法运用前缀和。此时我们引入差分序列来解决问题。
# 定义
设 ,特别地,假定 。称这个 序列为 差分序列 。
和前缀和序列一样,差分序列也可以在 时间内利用简单递推求出:
a[0] = 0;
for (int i = 1; i <= n; i ++) {
dif[i] = a[i] - a[i-1];
}
# 问题解决
相对于前缀和而言,差分要稍微复杂一些。
差分序列的设计是非常巧妙的,现在我们就试一下,对原序列的某个区间进行修改后,差分序列会发生什么变化。以一个 的序列为例,对区间 进行 操作。
修改前:
$\begin{aligned} a = {&a_1,& &a_2,& &a_3,& &a_4,& &a_5&} \ dif = {&a_1 - a_0,& &a_2 - a_1,& &a_3 - a_2,& &a_4 - a_3,& &a_5 - a_4&} \ \end{aligned}$
修改后:
$\begin{aligned} a = {&a_1,& &a_2 + x,& &a_3 + x,& &a_4,& &a_5&} \ dif = {&a_1 - a_0,& &a_2 - a_1 + x,& &a_3 - a_2,& &a_4 - a_3 - x,& &a_5 - a_4&} \ \end{aligned}$
如你所见,令原序列的区间 内的所有元素 ,只会令差分序列的 。也就是说,如果我们把对原序列的操作转化为对差分序列的操作,时间复杂度将会从 被优化到 ,这无疑是很有用的。
inline void modify(int l, int r, int x) {
dif[l] += x;
dir[r+1] -= x;
}
那么我们在修改完成后如何由差分序列回到原序列呢?容易发现 ,其实就是对差分序列求前缀和序列。也就是说,差分序列通常是和前缀和序列配合使用的。
b[0] = 0;
for (int i = 1; i <= n; i ++) {
b[i] = b[i-1] + dif[i];
}
# 应用
差分序列可用于解决不带查询的区间修改问题。注意这里强调了不带查询,这指的是不会频繁询问 的区间和,或很少询问。通常仅在所有修改结束后询问结果。如果问题中存在和修改相互交叉的频繁询问,那么差分通常难以胜任。
# 二维前缀和与二维差分
我们考虑将前缀和序列的模板问题扩展到二维情况:
给定一个 的矩阵 ,下标为 和 ,有 次操作,每次给定一个四元组 ,求 的值。
可以想象,如果我们能将前缀和序列也扩展到二维情况,即可解决该问题。
设 表示子矩阵 的和,即 。类似于一维的情况,在给定 的情况下,该序列可以在 时间内利用递推求出:
sum[0][0] = 0;
for (int i = 1; i <= n; i ++) {
sum[i][0] = 0;
}
for (int j = 1; j <= m; j ++) {
sum[0][j] = 0;
}
for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) {
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j];
}
这个递推方式比较巧妙,但说破了就很简单,如下图所示,子矩阵 被计算了两次,所以需要减掉一次,这其实就是你高中学过的组合数学的容斥原理。
那么二维差分也是类似的,对子矩阵 进行 操作,需要令差分序列:
inline void modify(int x1, int y1, int x2, int y2) {
dif[x2+1][y2+1] += x;
dif[x1][y2+1] -= x;
dif[x2+1][y1] -= x;
dif[x1][y1] += x;
}
类似于一维,修改完成后对 求个二维前缀和即可得到原矩阵上的元素的变化量。
# 高维前缀和
事实上,前缀和可以被推广到 维的情况,不过实际情况中几乎很少需要用到高维前缀和。
考虑到原理与一维二维相同,故对原理不再赘述,读者可自行推导三维前缀和的公式。
三维前缀和的直接公式实现:
// 求前缀和
void getsum(int x, int y, int z) {
sum[x][y][z] = cube[x][y][z]
+ sum[x-1][y][z] + sum[x][y-1][z] + sum[x][y][z-1]
- sum[x-1][y-1][z] - sum[x-1][y][z-1] - sum[x][y-1][z-1]
+ sum[x-1][y-1][z-1];
}
// 查询
int query(int x1, int y1, int z1, int x2, int y2, int z2) {
int res = sum[x2][y2][z2]
- sum[x1-1][y2][z2] - sum[x2][y1-1][z2] - sum[x2][y2][z1-1]
+ sum[x1-1][y1-1][z2] + sum[x1-1][y2][z1-1] + sum[x2][y1-1][z1-1]
- sum[x1-1][y1-1][z1-1];
return res;
}
三维前缀和的可扩展实现,下面的代码可直接扩展到 维:
// 求前缀和
void getsum(int x, int y, int z) {
sum[x][y][z] = cube[x][y][z];
for (int mask = 1; mask < 8; mask ++) {
int dx = ((mask >> 0) & 1);
int dy = ((mask >> 1) & 1);
int dz = ((mask >> 2) & 1);
int nx = x - dx;
int ny = y - dy;
int nz = z - dz;
int cnt = dx + dy + dz;
sum[x][y][z] += sum[nx][ny][nz] * (cnt % 2 == 1 ? 1 : -1);
}
}
// 查询
int query(int x1, int y1, int z1, int x2, int y2, int z2) {
int res = 0;
for (int mask = 0; mask < 8; mask ++) {
int dx = ((mask >> 0) & 1);
int dy = ((mask >> 1) & 1);
int dz = ((mask >> 2) & 1);
int x = dx ? (x1 - 1) : x2;
int y = dy ? (y1 - 1) : y2;
int z = dz ? (z1 - 1) : z2;
int cnt = dx + dy + dz;
res += sum[x][y][z] * (cnt % 2 == 0 ? 1 : -1);
}
return res;
}
(以下内容尚未排版)
# 树上差分
学习树上差分之前需要先学习树的LCA(最近公共祖先),请保证阅读前已经掌握LCA的基本知识。
事实上,差分序列可以被推广到有根树上,俗称为树上差分,同样是一项非常重要的技术。
如果我们将DFS回溯求子树和,视为树上前缀和的话,前缀和序列也可以被推广到有根树上。尽管如此,我们主要强调树上差分,毕竟“树上前缀和”是DFS的基本操作,没有什么特别值得再讲一遍的。
树上差分可以分为点差分和边差分两种,它们都是对树上的一条路径进行操作。其核心思想仍然和差分序列相同,因而对其原理不再赘述。
为便于描述,设表示树上两点和的LCA,设表示树上一点的父节点。
点差分:对树上从到的路径上的所有节点进行操作。
典型问题:给定一棵个节点的树,给定条树上的路径,求树上每个节点被多少条路径所覆盖。
dif[u] += x;
dif[v] += x;
dif[lca(u, v)] -= x;
dif[parent[lca(u, v)]] -= x;
边差分:对树上从到的路径上的所有边进行操作。虽说如此,但因为存储问题,我们通常把这里的边信息存储在其深度较大的节点上。
典型问题:给定一棵个节点的树,给定条树上的路径,求树上每条边被多少条路径所覆盖。
dif[u] += x;
dif[v] += x;
dif[lca(u, v)] -= 2*x;
可能树上差分的公式不太直观,但是自己画棵树推敲一下就能明白,其原理并不难。
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01