前缀和 & 差分
前缀和
定义
前缀和可以简单理解为「数列的前
C++ 标准库中实现了前缀和函数 std::partial_sum
,定义于头文件 <numeric>
中。
例题
解题思路
递推:B[0] = A[0]
,对于 B[i] = B[i-1] + A[i]
。
参考代码
#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;
}
二维/多维前缀和
常见的多维前缀和的求解方法有两种。
基于容斥原理
这种方法多用于二维前缀和的情形。给定大小为
类比一维的情形,
实现时,直接遍历
示例
考虑一个具体的例子。
这里,
同样的道理,在已经预处理出二位前缀和后,要查询左上角为
这可以在
在二维的情形,以上算法的时间复杂度可以简单认为是
洛谷 P1387 最大正方形
在一个
参考代码
#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)
逐维前缀和
对于一般的情形,给定
从上式可以看出,
三维前缀和的参考实现
#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;
}
因为考虑每一个维度的时候,都只遍历了整个数组一遍,这样的算法复杂度是
特例:子集和 DP
维度比较大的情形,经常出现在一类叫做 子集和 (SOS, Sum Over Subsets) 的问题中。这是高维前缀和的特例。
问题描述如下。考虑大小为
即
首先,子集和问题可以写成高维前缀和的形式。注意到,子集
所以,对子集求和,就是求这个
现在,可以直接使用前文所述的逐维前缀和的方法求得子集和。时间复杂度是
参考实现
#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;
}
子集和的逆操作需要通过 容斥原理 进行。子集和问题也是快速莫比乌斯变换的必要步骤之一。
树上前缀和
设
然后:
- 若是点权,
路径上的和为 。 -
若是边权,
路径上的和为 。 LCA 的求法参见 最近公共祖先。
差分
解释
差分是一种和前缀和相对的策略,可以当做是求和的逆运算。
这种策略的定义是令
性质
的值是 的前缀和,即 - 计算
的前缀和
它可以维护多次对序列的一个区间加上一个数,并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。
示例
譬如使
其中
最后做一遍前缀和就好了。
C++ 标准库中实现了差分函数 std::adjacent_difference
,定义于头文件 <numeric>
中。
树上差分
树上差分可以理解为对树上的某一段路径进行差分操作,这里的路径可以类比一维数组的区间进行理解。例如在对树上的一些路径进行频繁操作,并且询问某条边或者某个点在经过操作后的值的时候,就可以运用树上差分思想了。
树上差分通常会结合 树基础 和 最近公共祖先 来进行考察。树上差分又分为 点差分 与 边差分,在实现上会稍有不同。
点差分
举例:对树上的一些路径
对于一次
其中
可以认为公式中的前两条是对蓝色方框内的路径进行操作,后两条是对红色方框内的路径进行操作。不妨令
边差分
若是对路径中的边进行访问,就需要采用边差分策略了,使用以下公式:
由于在边上直接进行差分比较困难,所以将本来应当累加到红色边上的值向下移动到附近的点里,那么操作起来也就方便了。对于公式,有了点差分的理解基础后也不难推导,同样是对两段区间进行差分。
例题
洛谷 3128 最大流
FJ 给他的牛棚的
FJ 有
解题思路
需要统计每个点经过了多少次,那么就用树上差分将每一次的路径上的点加一,可以很快得到每个点经过的次数。这里采用倍增法计算 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;
}
习题
前缀和:
- 洛谷 B3612【深进 1. 例 1】求区间和
- 洛谷 U69096 前缀和的逆
- AtCoder joi2007ho_a 最大の和
- 「USACO16JAN」子共七 Subsequences Summing to Sevens
- 「USACO05JAN」Moo Volume S
二维/多维前缀和:
- HDU 6514 Monitor
- 洛谷 P1387 最大正方形
- 「HNOI2003」激光炸弹
- CF 165E Compatible Numbers
- CF 383E Vowels
- ARC 100C Or Plus Max
树上前缀和:
差分:
树上差分:
参考资料与注释
-
南海区青少年信息学奥林匹克内部训练教材 ↩
创建日期: 2018年7月11日