前缀和 & 差分

前缀和

定义

前缀和可以简单理解为「数列的前 项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。¹

C++ 标准库中实现了前缀和函数 std::partial_sum，定义于头文件 <numeric> 中。

例题

5
1 2 3 4 5

1 3 6 10 15

二维/多维前缀和

多维前缀和的普通求解方法几乎都是基于容斥原理。

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

1  3  7  10
6  9  15 22
12 18 29 45

例题

基于 DP 计算高维前缀和

基于容斥原理来计算高维前缀和的方法，其优点在于形式较为简单，无需特别记忆，但当维数升高时，其复杂度较高。这里介绍一种基于

设高维空间 共有 维，需要对 求高维前缀和 。令 表示同 后 维相同的所有点对于 点高维前缀和的贡献。由定义可知 ，以及 。

其递推关系为 ，其中 为第 维恰好比 少 的点。该方法的复杂度为 ，其中 为高维空间 的大小。

一种实现的伪代码如下：

for state
  sum[state] = f[state];
for(i = 0;i <= D;i += 1)
  for 以字典序从小到大枚举 state
    sum[state] += sum[state'];

树上前缀和

设 表示结点 到根节点的权值总和。
然后：

• 若是点权， 路径上的和为 。

• 若是边权， 路径上的和为 。

  LCA 的求法参见

  最近公共祖先。

差分

解释

差分是一种和前缀和相对的策略，可以当做是求和的逆运算。

这种策略的定义是令

性质

• 的值是 的前缀和，即
• 计算 的前缀和

它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。

C++ 标准库中实现了差分函数 std::adjacent_difference，定义于头文件 <numeric> 中。

树上差分

树上差分可以理解为对树上的某一段路径进行差分操作，这里的路径可以类比一维数组的区间进行理解。例如在对树上的一些路径进行频繁操作，并且询问某条边或者某个点在经过操作后的值的时候，就可以运用树上差分思想了。

树上差分通常会结合

点差分

举例：对树上的一些路径 进行访问，问一条路径 上的点被访问的次数。

对于一次 的访问，需要找到 与 的公共祖先，然后对这条路径上的点进行访问（点的权值加一），若采用 DFS 算法对每个点进行访问，由于有太多的路径需要访问，时间上承受不了。这里进行差分操作：

其中 表示 的父亲节点， 为点权 的差分数组。

可以认为公式中的前两条是对蓝色方框内的路径进行操作，后两条是对红色方框内的路径进行操作。不妨令 左侧的直系子节点为 。那么有 ，。可以发现实际上点差分的操作和上文一维数组的差分操作是类似的。

边差分

若是对路径中的边进行访问，就需要采用边差分策略了，使用以下公式：

由于在边上直接进行差分比较困难，所以将本来应当累加到红色边上的值向下移动到附近的点里，那么操作起来也就方便了。对于公式，有了点差分的理解基础后也不难推导，同样是对两段区间进行差分。

例题

习题

前缀和：

• 洛谷 B3612【深进 1. 例 1】求区间和
• 洛谷 U69096 前缀和的逆
• AT2412 最大の和
• 「USACO16JAN」子共七 Subsequences Summing to Sevens
• 「USACO05JAN」Moo Volume S

二维/多维前缀和：

• HDU 6514 Monitor
• 洛谷 P1387 最大正方形
• 「HNOI2003」激光炸弹

基于 DP 计算高维前缀和：

• CF 165E Compatible Numbers
• CF 383E Vowels
• ARC 100C Or Plus Max

树上前缀和：

• LOJ 10134.Dis
• LOJ 2491. 求和

差分：

• 树状数组 3：区间修改，区间查询
• P3397 地毯
• 「Poetize6」IncDec Sequence

树上差分：

• 洛谷 3128 最大流
• JLOI2014 松鼠的新家
• NOIP2015 运输计划
• NOIP2016 天天爱跑步

参考资料与注释