前缀和 & 差分
前缀和
定义
前缀和可以简单理解为「数列的前
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)
基于 DP 计算高维前缀和
基于容斥原理来计算高维前缀和的方法,其优点在于形式较为简单,无需特别记忆,但当维数升高时,其复杂度较高。这里介绍一种基于 DP 计算高维前缀和的方法。该方法即通常语境中所称的 高维前缀和。
设高维空间
其递推关系为
一种实现的伪代码如下:
树上前缀和
设
然后:
- 若是点权,
路径上的和为 。 -
若是边权,
路径上的和为 。 LCA 的求法参见 最近公共祖先。
差分
解释
差分是一种和前缀和相对的策略,可以当做是求和的逆运算。
这种策略的定义是令
性质
的值是 的前缀和,即 - 计算
的前缀和
它可以维护多次对序列的一个区间加上一个数,并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。
示例
譬如使
其中
最后做一遍前缀和就好了。
C++ 标准库中实现了差分函数 std::adjacent_difference
,定义于头文件 <numeric>
中。
树上差分
树上差分可以理解为对树上的某一段路径进行差分操作,这里的路径可以类比一维数组的区间进行理解。例如在对树上的一些路径进行频繁操作,并且询问某条边或者某个点在经过操作后的值的时候,就可以运用树上差分思想了。
树上差分通常会结合 树基础 和 最近公共祖先 来进行考察。树上差分又分为 点差分 与 边差分,在实现上会稍有不同。
点差分
举例:对树上的一些路径
对于一次
其中
可以认为公式中的前两条是对蓝色方框内的路径进行操作,后两条是对红色方框内的路径进行操作。不妨令
边差分
若是对路径中的边进行访问,就需要采用边差分策略了,使用以下公式:
由于在边上直接进行差分比较困难,所以将本来应当累加到红色边上的值向下移动到附近的点里,那么操作起来也就方便了。对于公式,有了点差分的理解基础后也不难推导,同样是对两段区间进行差分。
例题
洛谷 3128 最大流
FJ 给他的牛棚的
FJ 有
解题思路
需要统计每个点经过了多少次,那么就用树上差分将每一次的路径上的点加一,可以很快得到每个点经过的次数。这里采用倍增法计算 LCA,最后对 DFS 遍历整棵树,在回溯时对差分数组求和就能求得答案了。
参考代码
#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;
}
习题
前缀和:
- 洛谷 B3612【深进 1. 例 1】求区间和
- 洛谷 U69096 前缀和的逆
- AtCoder joi2007ho_a 最大の和
- 「USACO16JAN」子共七 Subsequences Summing to Sevens
- 「USACO05JAN」Moo Volume S
二维/多维前缀和:
基于 DP 计算高维前缀和:
树上前缀和:
差分:
树上差分:
参考资料与注释
-
南海区青少年信息学奥林匹克内部训练教材 ↩
创建日期: July 11, 2018