【日报】差分与前缀和，但是加上了一些拓展
囧仙
2022-06-27 10:33:54
## 前言
因本人尚菜，不太会数学上的有限微积分，所以本篇文章主要是谈谈差分在 $\text{OI}$ 题中的应用。同时为了降低本文的阅读难度，本文**尽量**只谈差分思想本身，不会去涉及「差分之后再拿个高级数据结构进行维护」这样的内容。
图丑，轻喷。
## 正文
### 差分
我们定义数组 $a$ 的差分数组 $\Delta a$，满足下式：
$$\Delta a_n=\begin{cases}a_n-a_{n-1}& n>1\cr a_1 & n=1\end{cases}$$
> **注**：有限微积分里通常定义 $\Delta a_n=a_{n+1}-a_n$，但用这种定义做 $\text{OI}$ 题不太方便，因此本文采取如上定义方式。另外，通常可以令 $a_0=0$，这样可以统一定义 $\Delta a_n=a_n-a_{n-1}$，写代码的时候也比较方便。
如图所示，一个差分数组的例子。
### 前缀和
考虑 $\Delta a$ 数组的前缀和。容易发现：
$$\sum_{i=1}^n\Delta a_i=\sum_{i=1}^n(a_i-a_{i-1})=\sum_{i=1}^n a_i-\sum_{i=1}^{n-1}a_{i}=a_n$$
因此可以认为，**差分和前缀和是一对互逆的运算**。
### 差分的简单应用
例 $1$：
> 已知长度为 $n$，初始值均为 $0$ 的数组 $a$。现在有 $m$ 次操作。每次操作给定 $l_i,r_i,w_i$，表示将 $a_{l_i},a_{l_i+1},\cdots a_{r_i}$ 依次加上 $w_i$。求**最终** $a$ 数组的值。
> $1\le n\le 10^7$，$1\le m\le 3\times 10^5$。
对于每个询问，暴力枚举 $l_i,l_i+1\,\cdots r_i$，进行加法操作，复杂度为 $\mathcal O(nm)$，无法通过；但是可以考虑 $a$ 数组的差分数组 $\Delta a$。
如图所示，在 $a$ 数组的 $3\sim 7$ 位置依次加上 $4$ 之后，它的差分数组 $\Delta a$ 仅仅修改了两个位置：$3$ 和 $8$。一般地，在 $a$ 数组的 $l\sim r$ 位置依次加上 $w$，对于 $\Delta a$ 数组只会发生两个改变：$\Delta a_l$ 的值增加了 $w$，而 $\Delta a_{r+1}$ 的值减少了 $w$。
另外值得注意的是，即使 $a_i$ 数组内有初始值/已经经过了若干次修改操作，那么现在想要让 $a$ 数组的 $l\sim r$ 位置增加 $w$，同样也是让 $\Delta a$ 数组的 $l$ 位置增加 $w$，在 $r+1$ 位置减少 $w$。
这启示我们，对于每个操作，将 $\Delta a_{l}$ 增加 $w$，将 $\Delta a_{r+1}$ 减小 $w$，最后统一做一次前缀和，就能得到最终的答案。
时间复杂度为 $\mathcal O(n+m)$，可以通过本题。
值得注意的是，一般差分都会与前缀和同时使用。并且这类题目一般只要计算所有操作结束后的值（当然也有很多在线的题，不过通常需要使用更高级的数据结构进行维护，这里不讨论）。
### 二次差分的简单应用
例 $2$：[$\text{P4231}$ 三步必杀](https://www.luogu.com.cn/problem/P4231)
> 已知长度为 $n$，初始值均为 $0$ 的数组 $a$。现在有 $m$ 次操作。每次操作给定 $l,r,s,e$，使 $a_l,a_{l+1},\cdots a_r$ 依次加上「首项为 $s$，末项为 $e$ 的等差数列」中的项，保证这些项均为整数。要求最终 $a$ 数组。
> $1\le n\le 10^7$，$1\le m\le 3\times 10^5$。
同样考虑 $a$ 数组的差分数组。这里给出一个例子：
发现在本题中，对于每个操作差分数组 $\Delta a_i$ 发生修改的数字的个数为 $r-l+1$，直接对于每次操作暴力修改差分数组，总时间复杂度为 $\mathcal O(nm)$，是不能通过该题的。但是可以发现，**差分数组中的第 $l+1$ 项至第 $r$ 项相同**，相同的值为等差数列的公差。
因此考虑对 $\Delta a_i$ 再进行一次差分，得到如下结果：
容易发现，我们要修改的位置一共只有 $4$ 个，分别为 $\Delta^2a_l,\Delta^2a_{l+1},\Delta^2a_r,\Delta^2a_{r+1}$。每次操作时，我们只更新 $\Delta ^2a$ 的值；所有操作结束后对 $\Delta ^2a$ 求一次前缀和，得到 $\Delta ^1a$；再对 $\Delta ^1a$ 求一次前缀和，得到最终的 $a$ 数组。
考虑这 $4$ 个修改对应的值。设这个等差数列公差为 $d$，显然 $\Delta^2a_l$ 处加上 $w$，$\Delta ^2a_{l+1}$ 处加上 $w+1$，$\Delta ^2{a_r}$ 处减去 $e+d$，$\Delta^2 a_{r+1}$ 处加上 $e$。
不觉得这样有点麻烦？事实上一个更好的做法是，我们只关心 $\Delta ^1a$ 当中 $(l+1)\sim r$ 这一部分，于是新开一个数组 $b$，令 $b_l$ 加上 $s$，$b_{r+1}$ 减去 $e$，在所有操作结束后，$\Delta^2 a$ 存储的值已经更新到 $\Delta ^1a$ 上以后，再把 $b$ 存储的值增加到 $\Delta ^1a$ 上。依然是上面那个例子：
虽然多开了一个数组，但它的优点在于容易调试、不容易出错。
### 二维前缀和&二维差分
#### 1. 基于容斥的做法
例 $3$：
> 已知长宽分别为 $n,m$ 的二维矩形 $a$，每个格子里都有值为 $a_{i,j}$。现在有 $q$ 次询问，每次询问给定四个数 $(x_1,y_1),(x_2,y_2),w$，求出左上角为 $(x_1,y_1)$，右下角为 $(x_2,y_2)$ 的矩形当中，每个数字之和。
> $1\le n,m\le 5\times 10^3$，$1\le q\le 3\times 10^5$。
考虑二维前缀和。
$$S_{n,m}=\sum_{i=1}^n\sum_{j=1}^m a_{i,j}$$
假设现在需要计算绿色矩形内所有元素之和。记黄色区域、蓝色区域、橘色区域、绿色区域元素之和分别为 $A,B,C,D$，容易发现：
$$
\begin{cases}
\begin{aligned}
&S_{x_2,y_2}&=&A+B+C+D \cr
&S_{x_1-1,y_1-1}&=&A \cr
&S_{x_1-1,y_2}&=&A+B \cr
&S_{x_2,y_1-1}&=&A+C \cr
\end{aligned}
\end{cases}
$$
解得：
$$D=S_{x_2,y_2}-S_{x_2,y_1-1}-S_{x_1-1,y_2}+S_{x_1-1,y_1-1}$$
同时也可以考虑不同区域的覆盖次数来理解该等式的含义。
于是只要求得所有 $S_{x,y}$ 即可 $\mathcal O(1)$ 回答每个询问。下面考虑如何计算 $S_{x,y}$。
假定在这之前我们已经计算好了以 $(1,1)$ 为左上角，$(x,y)$ 为右下角的矩阵中除了 $S_{x,y}$ 以外的每个 $S_{i,j}$，那么可以发现：
$$S_{x,y}=S_{x-1,y}+S_{x,y-1}-S_{x-1,y-1}+a_{x,y}$$
只需要根据上文中 $D$ 的表达式，令 $x_1=x-1,y_1=y-1,x_2=x,y_2=y$ 即可得到该式。
例 $4$：
> 已知长宽分别为 $n,m$ 的二维矩形 $a$，现在有 $q$ 次操作，每次操作给定五个数 $(x_1,y_1),(x_2,y_2),w$，让左上角为 $(x_1,y_1)$，右下角为 $(x_2,y_2)$ 的矩形当中，每个数字增加 $w$。
> $1\le n,m\le 5\times 10^3$，$1\le q\le 3\times 10^5$。
对于二维数组，我们同样可以定义它的差分。对于二维数组 $a$，我们希望它的二维差分数组 $\Delta a$ 满足以下条件：
$$a_{x,y}=\sum_{i=1}^x\sum_{j=1}^y \Delta a_{i,j}$$
显然 $a$ 就是 $\Delta a$ 的二维前缀和。根据上文求得的等式，可以很快得到：
$$\Delta a_{x,y}=a_{x,y}-a_{x-1,y}-a_{x,y-1}+a_{x-1,y-1}$$
这有什么用呢？考虑修改 $\Delta a_{x,y}$ 对 $a$ 产生的影响。令 $\Delta a_{x,y}$ 加上 $w$，可以发现对于 $i=x,x+1,\cdots n$，$j=y,y+1,\cdots m$，$a_{i,j}$ 都加上了 $w$。现在想要让左上角、右下角分别为 $(x_1,y_1),(x_2,y_2)$ 的矩形内所有元素加上 $w$，只要 $\Delta a_{x_1,y_1}$ 加上 $w$，$\Delta a_{x_1,y_2+1}$ 减去 $w$，$\Delta a_{x_2+1,y_1}$ 加上 $w$，$\Delta a_{x_2+1,y_2+1}$ 加上 $w$ 即可。读者可以自行画图验证，这里不再赘述。
#### 2. 基于多次差分&前缀和的做法
考虑 $x$ 方向做一次差分，$y$ 方向再做一次差分，那么就可以发现一共只有四个格子需要修改。由于差分操作与前缀和操作互逆，因此只需要在二维差分数组上修改四个格子的值，再往回做两次前缀和即可。
这种做法的优点就在于比起容斥做法要简单得多，不需要考虑各种集合之间的交并关系。在下面一个例子中，我们还将看到这种做法的优越性。
### 多维前缀和&二维差分
例 $5$：
> 已知一个 $k$ 维矩形 $a$，每一维的范围为 $1\sim d_i$。现在有 $m$ 次操作，每次操作给定 $k$ 个整数 $c_1,c_2,\cdots c_k$，以及一个整数 $w$，对于所有 $i_1=1,2,\cdots c_1$，$i_2=1,2,\cdots c_2$，$\cdots$，$i_k=1,2,\cdots c_k$，使 $a_{i_1,i_2,\cdots i_k}$ 加上 $w$。求出所有操作过后的 $a$。
> $1\le k \le 10$，$\prod d_i\le 10^6$，$1\le m\le 3\times 10^4$。
因为笔者太菜，想象不出四维空间，所以只能画个三维的图凑合凑合。
如图是 $k=3$ 的情况。现在需要给绿色区域内每个数字加上 $w$。于是可以先将整个长方体沿着 $x$ 方向做一次差分，得到了如下结果：
发现三维问题转化为了两个二维问题。考虑继续沿着 $y$ 方向做一次差分。
再沿着 $z$ 方向做一次差分。
由此一共只需要修改 $2^k=8$ 个点。途中绿色的点需要增加 $w$，蓝色的点需要减小 $w$。将此推广到一般情形，每次操作需要修改 $2^k$ 个点，因此修改的总时间复杂度为 $\mathcal O(m\cdot 2^k)$；最后我们需要做 $k$ 次前缀和，总时间复杂度为 $\mathcal O(k\cdot \prod d_i)$。
但是可以发现，容斥做法在最终求前缀和时，$k$ 维矩形中的每个点都需要进行 $2^k$ 次操作，而且容斥的系数不太好想（限于篇幅，这里不展开了。~~其实是我太菜算不出来~~），总时间复杂度为 $\mathcal O(m\cdot 2^k+2^k\cdot \prod d_i)$。即使使用差分，那么有效的点的个数也有 $2^k\cdot m$ 个，时间复杂度劣于 $k$ 次差分与 $k$ 次前缀和。
### 奇怪的数列的差分
例 $6$：[$\text{P6308}$ 「Wdsr-1」笨蛋结构](https://www.luogu.com.cn/problem/P6308)
> 已知一个长度为 $n$ 的数组 $a$，初始值为 $0$。现在有 $q$ 次操作，每次操作给定整数 $s,l,w,k$，对于 $i=1,2,\cdots l$，$a_{s+i-1}$ 的值加上 $w\cdot i^k$。
> $n\le 5\times 10^5$，$1\le k\le 9$，$1\le q\le 10^6$。
现在假设我们要对一段数字分别加上数组 $a=\{1^k,2^k,\cdots l^k\}$ 中的元素。对它做一次差分，得到：
$$\Delta a_n=\begin{cases}n^k-(n-1)^k& n< s+l\cr -n^k & n=s+l\end{cases}$$
考虑用二项式定理把第一个式子直接展开：
$$\begin{aligned}
(n-1)^k&=\sum_{i=0}^k\binom{k}{i}n^i\cdot (-1)^{k-i} \cr
n^k-(n-1)^k&=\sum_{i=0}^{k-1}\binom{k}{i}n^i\cdot (-1)^{k-i+1} \cr
&=\sum_{i=0}^{k-1}\binom{k}{i}(-1)^{k-i+1}\cdot n^i
\end{aligned}$$
记 $f(i,k)=\binom{k}{i}(-1)^{i-k}$。可以发现我们要对 $a$ 执行的操作，可以拆解成对 $\Delta^1 a$ 进行的操作，当然，对 $\Delta ^1 a$ 进行的操作也可以转化为对 $\Delta^2 a$ 等差分数组进行的操作。具体而言，记 $\operatorname{solve}(w,s,l,k,d)$ 表示进行一次对 $\Delta ^d a$ 执行「第 $s$ 项开始依次加上 $w\cdot i^k$」的操作，那么 $\operatorname{solve}(w,s,l,k,d)$ 可以被分解为这样一些操作：
- $\Delta ^{d+1} a_{s+l}$ 减去 $w\cdot l^k$。
- 对于 $i=0,1,\cdots k-1$，执行 $\operatorname{solve}(w\cdot f(i,k),s,l,i,d+1)$。
递归的边界，就是 $k=0$。此时只要 $\Delta ^{d+1}a_s$ 加上 $w$，$\Delta ^{d+1}a_{s+l}$ 减去 $w$ 即可。
如果直接这样做，复杂度较高，考虑优化。注意到这样一个重要性质：
- $\operatorname{solve}(w,s,l,k,d)$ 执行完毕后，差分数组上仅有第 $s$ 个元素和第 $s+l$ 个元素会被修改。
诸如，以下是执行 $\operatorname{solve}(1,3,5,3,0)$ 后的结果：
> **注**：绿色和蓝色部分是实际操作时修改的差分数组，黄色部分是所有操作结束后，「按照自下而上的顺序，计算前缀和并累加到上一级差分数组」后的结果。
这是容易证明的。考察我们将操作拆分的过程，可以发现每次拆分后 $s$ 和 $l$ 的值都不会发生改变；再考察修改的过程，也能发现要么在 $s$ 处修改，要么在 $s+l$ 处修改。
可以发现，绿色部分仅仅和 $k$ 有关。因此可以通过打表快速求出所有绿色部分的情况。主要是蓝色部分。考虑蓝色部分的实际意义：**在对差分数组计算前缀和时，加上蓝色部分的数后，当前位置的数字恰好变为** $\bm 0$。
还是刚才的例子：
现在考虑在第三列第四行加上 $1$，那么第八列应该减去的数字。观察黄色区域：**这不就是杨辉三角吗**？第 $i$ 行第 $j$ 列的数字，等于第 $i$ 行第 $j-1$ 列的数字，加上第 $i+1$ 行第 $j$ 列的数字。这与组合数的递推公式如出一辙：
$$\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$$
因此，要在第 $s$ 列 $i$ 行增加的数字 $w$，就要在第 $s+l$ 列 $j$ 行减去 $w\cdot \dbinom{l+i-j}{i-j}$。
第 $s$ 列要增加的数字是可以预处理出来的。组合数也是可以预处理出来的。因此可以用 $\mathcal O(k^2)$ 的时间复杂度执行每次操作。总时间复杂度为 $\mathcal O(n\cdot k_{\max}+qk_{\max}^2)$。
---
例 $7$：[$\text{P7705}$ 「Wdsr-2.7」天才⑨与数学递推式](https://www.luogu.com.cn/problem/P7705)
> 给定一个数组 $\{K_1,K_2\cdots,K_m\}$ ，由此得到一个递推式：
> $$F_t=\sum_{i=1}^m K_i\times F_{t-i} \quad (t> m)$$
> 现在有 $m$ 次对答案数组 $\{A_i\}$ 的操作。每次给定一个 $\{F_i\}$ 的前 $m$ 项，然后让 $A_a\gets A_a+F_1,A_{a+1}\gets A_{a+1}+F_2\cdots A_{b}\gets A_b+F_{b-a+1}$ 。输出最后的 $A_i$。
> $1\leq n\le 1\times 10^6$，$1\le q \leq 1.2 \times 10^5$，$1 \leq m \leq 15$，$1 \leq a_i,k_i,c_i,p \leq 10^8$。
首先考虑推广题目中的无限数列的生成方式，将它认为是对一个**数组**的变换操作（类似于代码当中的函数）。比如根据 $A$ 生成这个数列，就记为 $\mathcal F(A)$ 。生成的数列的第 $i$ 项记为 $\mathcal F(A)_i$ 。给出以下定义：
$$\mathcal F(A)_i=\begin{cases}
A_i+\sum_{i=1}^kK_i\times \mathcal F(A)_{n-i+1} & i>0 \cr
0 & i\le 0
\end{cases}$$
要注意的是，这种方法生成的数列并不等价于题面中给出的式子，因为 $\mathcal F(A)_2$ 的值与 $A_1$ 有关， $\mathcal F(A)_3$ 的值与 $A_1$ 和 $A_2$ 有关，等等。
对于递推式，有一个很好的性质：假如有两个数组 $\{P_i\}$ 和 $\{Q_i\}$ ，那么有：
$$\mathcal F(P)+\mathcal F(Q)=\mathcal F(P+Q)$$
（其中，两个数列相加表示其对应项分别相加，两个数列相等当且仅当它们每一项都相等）怎么证明呢？
考虑归纳法。显然，对于第 $1$ 项的值是对应相等的，即满足 $\mathcal F(P)_1+\mathcal F(Q)_1=\mathcal F(P+Q)_1$ 。设结论对于前 $k$ 项成立，那么对于第 $n=k+1$ 项，有：
$$\begin{aligned}
&\mathcal F(P)_{n+1}=P_i+\sum_{i=1}^m K_i\times \mathcal F(P)_{n+1-i}\cr
&\mathcal F(Q)_{n+1}=Q_i+\sum_{i=1}^m K_i\times \mathcal F(Q)_{n+1-i}\cr
\end{aligned}$$
两式相加，容易得到：
$$\begin{aligned}
\mathcal F(P)_{n+1}+\mathcal F(Q)_{n+1}&=P_i+Q_i+\sum_{i=1}^m K_i\times \mathcal F(P)_{n+1-i}+\sum_{i=1}^m K_i\times \mathcal F(Q)_{n+1-i}\cr
&=(P_i+Q_i)+\sum_{i=1}^m K_i(\mathcal F(P)_{n+i-1}+\mathcal F(Q)_{n+i-1})\cr
&=(P_i+Q_i)+\sum_{i=1}^m K_i\times \mathcal F(P+Q)_{n+i-1}\cr
&=\mathcal F(P+Q)_i
\end{aligned}$$
于是对于 $n=k+1$ 仍然成立。所以原命题成立。
这个结论可以启发我们，假如我们要对若干个数组进行 $\mathcal F$ 操作后相加，那就可以将它们先相加为一个数组 $S$ 后再根据定义求出 $\mathcal F(S)$ 。
当然，这样做还有两个小问题要解决。
- 首先，使用 $\mathcal F(F)$ 生成的数列，它的前 $m$ 项并不是 $F$ 的前 $m$ 项。因此我们只要试图对 $F$ 进行改造，构造出一个 $\mathring F$ 使得 $\mathcal F(\mathring F)$ 的前 $m$ 项恰好为 $F$ 的前 $m$ 项。
举个例子。比如 $m=3,K=\{1,2,3\}$ ，我们有一个初始序列 $F=\{1,1,4\}$ ，那么有：
$$\mathcal F(F)=\{1,2,8,15,37,91,210,503,1196,\cdots\}$$
然而，我们希望得到的数列应该是：
$$\{1,1,4,9,20,50,117,277,661,\cdots\}$$
不过，解决方法很简单：由于我们预先知道实际序列的前 $m$ 项，所以对于 $S$ 的第 $t$ 项，可以计算出第 $1,2,\cdots t-1$ 项对第 $t$ 项的贡献，然后让 $S_t$ 减去这个贡献即可，即：
$$\mathring F_t=F_t-\sum_{i=1}^{t-1}K_iF_{t-i}$$
- 此外，我们生成的数列都是无穷长的，也就是生成到了 $[a,+\infty)$ 上。但我们只要 $[a,b]$ 这一段。不过，这个问题也很容易处理。我们计算出 $b+1,b+2,\cdots b+m$ 位置上将会生成的值，然后设法在 $S$ 上减去即可。
首先预处理出 $\mathcal F(\{1,0,0,\cdots\})$ 的前 $n+m$ 项，记为 $E_i$ 。那么，在 $F$ 上第 $i$ 位的数字 $F_i$ 对 $\mathcal F(S)$ 第 $j$ 位的贡献就应该是 $E_{j-i}\times F_i$ 。于是可以求出 $G$ ：
$$G_i=-\sum_{j=1}^m\mathring F_{j}\times E_{b-a+j-i+1}$$
同理，可以计算出 $\mathring G$ 。最后，对 $S$ 进行操作：
$$\begin{aligned}
S_{a+i-1}&\gets S_{a+i-1}+\mathring F_{i} & 1\le i\le m \cr
S_{b+i}&\gets S_{b+i}+\mathring G_{i} & 1\le i\le m
\end{aligned}$$
解决了这两个问题，最后的结果就是 $\mathcal F\{S\}$ 。
### 奇形的图形的差分
例 $8$：[$\text{P8008}$ 「Wdsr-3」迷途竹林](https://www.luogu.com.cn/problem/P8008)
> 给定一个 $n$ 个顶点的多边形（不一定是凸的，但保证是简单多边形）。现在填充无穷个间距相等的平行线，询问多边形中平行线的总长度（可以参考图片）。
容易发现，对多边形以及其中的斜线进行旋转并不会对答案造成任何影响。因此第一步可以将所有斜线旋转至水平，便于进行下一步讨论。
关于线段的旋转，这里提供两种思路：
- 第一种思路是，将笛卡尔坐标系转为极坐标系，让极角加上需要旋转的角度后再转换回来。具体而言，对于点 $(x_0,y_0)$，它的极径为 $r=\sqrt{x_0^2+y_0^2}$，极角为 $\theta=\arctan \dfrac{y_0}{x_0}$（关于极角的计算，可以使用 $\text{C++}$ 中的函数 $\verb!atan2(y,x)!$，**注意 $\bm x$ 坐标和 $\bm y$ 坐标的顺序**）。将极坐标 $(r,\theta)$ 转换为笛卡尔坐标系中的坐标，即为 $(r\cdot \cos\theta,r\cdot \sin \theta)$。
- 第二种思路是，把平面看成复平面，利用复数乘法「辐角相加，模长相乘」的特点，把 $x_0+\mathrm iy_0 $ 乘上辅角为 $\theta$，模长为 $1$ 的复数 $\cos\theta+\mathrm i\sin\theta$。
不旋转坐标系，直接硬上应该也行；我没试过。
---
容易发现，一条橙色线段可以认为是从右侧某条方向向下的线段发出、打到了左侧某条方向向上的线段上的。因此不妨考虑差分的思想：
以顺时针为正方向，在左侧随便取个竖直线段作为基准线，计算由红色线段向基准线发出的所有橙色线段的长度之和。方向向下时对答案的贡献为正，方向向上时对答案的贡献为负。容易发现，两者之和就是这两条线段之间的橙色线段长度之和。因此问题简化为了，计算一条线段发出来的到达左侧基准线的橙色线段的长度之和。
由于题目中保证了斜线不会与多边形的任何边平行，因此可以认为红色线段的斜率必然不为 $0$。设线段的两个端点为 $A(x_1,y_1)$ 和 $B(x_2,y_2)$。可以计算出斜线两两之间的距离 $d=a\sin\theta$，那么橙色线段都可以表示为 $y=kd,k\in \Bbb Z$。由于 $y_1<kd<y_2$，因此可以解出 $k$ 的最小值为 $\left\lceil\dfrac{y_1}{d}\right\rceil$，最大值为 $\left\lfloor\dfrac{y_2}{d}\right\rfloor$（这里并不需要强调 $kd$ 与 $y_1,y_2$ 是否可以相等，因为你可以给每个点加上个微小的 $y$ 方向偏移量如 $10^{-9}$，来避开此类问题）。
现在要做的，是根据线段 $AB$ 的解析式算出 $k$ 最小、最大的情况下的 $x$ 坐标。
$$
\frac{x-x_1}{x_2-x_1}=\frac{y-y_1}{y_2-y_1} \Rightarrow x=\frac{x_2-x_1}{y_2-y_1}(y-y_1)+x_1
$$
因为基准线可以随便取，因此这里直接取 $y$ 轴作为基准线。计算出 $x_{\mathrm{left}}$ 和 $y_{\mathrm{right}}$ 后可以使用等差数列求和进行计算。已知起始值、终止值、项数（$t=\dfrac{|y_1-y_2|}{d}$），那么有：
$$\text{贡献}=\frac{(x_{\mathrm{left}}+x_{\mathrm{right}})\cdot t}{2}$$
（事实上，如果 $y_1>y_2$ 就能说明贡献为正；如果 $y_1<y_2$ 就能说明贡献为负。因此在计算 $t$ 的时候去掉绝对值就能考虑到贡献的正负）。
统计所有边的贡献即可得到答案。
---
例 $9$：[$\text{P8228}$ 「Wdoi-5」模块化核熔炉](https://www.luogu.com.cn/problem/P8228)
> 给定一个边长为 $n$ 的正六边形阵列。现在有 $m$ 次操作，每次将一整个边长为 $r$ 的正六边形区域内每个元素增加 $w$。输出最后六边形阵列每个的元素（可以参考图片）。
> $1\le n \le 800$，$1\le m\le 3\times 10^5$。
我们可以发现，在一个正六边形阵列里，可以按照某个方向进行变换，将一个平行四边形区域转化为矩形区域：
因此，这里考虑将给我们的坐标进行**坐标转换**。
具体而言，我们新建这样两个坐标系。
按照原点的方位，我们分别将它们称呼为**左系**和**右系**。先讨论如何将题目给定的坐标系（称呼为标准系）的坐标转换为左系和右系当中点的坐标。假设给定的坐标为 $(x_0,y_0,z_0)$。
- 容易发现，在标准系当中，每向 $x$ 方向走一格会导致左系的 $x$ 增加 $1$，$y$ 减小 $1$；每向 $y$ 方向走一格会导致左系的 $y$ 增加 $1$；每向 $z$ 方向走一格会导致左系的 $x$ 减小 $1$。考虑到标准系中原点的坐标在左系中为 $(n,n)$，那么标准系中的坐标 $(x_0,y_0,z_0)$ 转换为左系坐标就是 $(x_0-z_0+n,y_0-x_0+n)$。
- 同时发现，在标准系当中，每向 $x$ 方向走一格会导致右系的 $x$ 增加 $1$；每向 $y$ 方向走一格会导致右系的 $y$ 增加 $1$；每向 $z$ 方向走一格会导致右系的 $x$ 减小 $1$，$y$ 减小 $1$。考虑到标准系中原点的坐标在右系中为 $(n,n)$，那么标准系中的坐标 $(x_0,y_0,z_0)$ 转换为左系坐标就是 $(x_0-z_0+n,y_0-z_0+n)$。
这张图是对一个**右系**进行矩形变换后的结果。容易发现，在原图当中一个向右倾斜的平行四边形区域，可以被被转化为右系当中的一个矩形。同理，我们可以对左系进行矩形变换：
因此，我们可以将一个六边形网格图中，一个向左倾斜的平行四边形区域的区间加，转化为**左系**所对应的那个矩形里的一个矩形加。
知道这些，这条题目就非常简单了。现在假设我们需要对原图当中这样一个大的正六边形区域执行加法操作：
那么它可以被转换为这样四个图形之间的拼接：
其中，红色部分代表的是正值，蓝色部分代表的是负值。它可以被转化为两个左系当中的矩形加，以及两个右系当中的矩形加。
记得处理一下矩阵的边界超出左系/右系的情况，那么这题就做完了。
### 树上差分略谈
~~因为笔者不会啥高级的树上差分操作，只能凑凑字数了~~。
在这里我就谈论两种前缀和的计算方式：
- 第一种方法，节点 $u$ 的前缀和为它子树内所有节点的权值之和。形式化地表述，则是：
$$S_u=\sum_{v\in \mathrm{subtree}(u)} w_v$$
- 第二种方法，节点 $u$ 的前缀和为它所有祖先（包括他自己）的权值之和。同样给出形式化的表述：
$$S_u=\sum_{\begin{aligned}&\scriptsize v\text{ is a father of }u \cr[-5pt] & \scriptsize \text{or }v=u\end{aligned}} w_v$$
这两种方法分别有啥用呢？
例 $10$：[$\text{P3384}$ 【模板】轻重链剖分/树链剖分](https://www.luogu.com.cn/problem/P3384)，但是只要回答一次
> 已知一棵包含 $n$ 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：
> - `1 x y z`，表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$。
> - `2 x z`，表示将以 $x$ 为根节点的子树内所有节点值都加上 $z$。
> 输出所有操作结束后，每个结点的权值。
考虑第一种方法计算前缀和，那么给一个节点加上 $w$ 后，对其他节点前缀和的影响如下：
也就是说，这种方法可以将 $1\sim u$ 上所有节点的权值加上 $w$。至于要将 $u\sim v$ 路径上的节点的权值加上 $w$，那么只要在 $u,v$ 处权值加上 $w$，在 $\operatorname{lca}(u,v),\operatorname{fa}(\operatorname{lca}(u,v))$ 处权值减去 $w$，就可以做到。瓶颈在于计算最近公共祖先。不过既然都离线了，那用 $\text{tarjan}$ 算法用近似均摊 $\mathcal O(1)$ 的复杂度算下就行。所以这种前缀和方法可以解决操作 $1$。
考虑第二种方法计算前缀和，那么给一个节点加上 $w$ 后，对其他节点前缀和的影响如下：
显然可以用来解决操作 $2$。
对于两种操作，分别开一棵树，每次操作时修改对应的树上的节点的权值，最后分别做一次前缀和即可。那么我们就在 $\mathcal O(n\cdot \alpha(n))$ 的复杂度解决了这样一个弱化了的树剖问题。