差分与前缀和 - 1

前情提要：学弟说想学莫反，于是偶先写一个入门教程，后面再写不入门的。欢迎各人提出建议，请大力喷！
差分、前缀和作为微分、积分在离散空间中的对应情势，照旧相当有用的。
Part 1

1D 序列 / 一维线性空间

这是我们最熟悉的场景，说给定了一个序列 \(a=(a_1,a_2 \dots a_n)\)，可以定义差分、前缀和两种运算/算子。
定义差分算子 \(\Delta\) 作用效果是 \((\Delta a)_i = a_i - a_{i-1}\)。
定义前缀和算子 \(\Delta^{-1}\) 作用效果是 \((\Delta^{-1} a)_i = \sum_{x=1}^i a_x\)。
这个符号特别难打，后面基本就不用了，只是想说这两种操纵是互逆的。
这里注意一个细节，学过微积分的同砚会知道，我们先差分再前缀和，应该会多出来一个不能确定的 \(C\)。
举个例子就是 \((1,2,3), (10,11,12)\) 的差分都是 \((1,1)\)，再做前缀和得到的是 \((C, C+1, C+2)\) 这样一簇东西。
这样一来，我们的差分算子不是单射，疑似有点太垃圾了。
以是我们总是额外规定 \(a_0 = 0\)，这样在差分的时候，可以额外保存这个常数 \(C\) 的具体信息。
这样一来  \(\Delta\) 和 \(\Delta^{-1}\) 之间也就可以交换次序了，即 \(\Delta \Delta^{-1} = \Delta^{-1} \Delta = I\)。固然这个很平凡。
Q1：给定长为 \(n\) 的序列 \(a_i\)，有 \(q\) 次操纵，支持区间加一个数，全部结束后，你需要输出序列。
Sol：维护差分序列，最后前缀和还原返来就行，\(O(n+q)\)。
Q2：给定长为 \(n\) 的序列 \(a_i\)，有 \(q\) 次操纵，支持区间加等差数列，全部结束后，你需要输出序列。
Sol：维护二阶差分序列，最后二阶前缀和还原返来就行，\(O(n+q)\)。
反演

反演的意思是，通过一个已知求和的序列，反向把原序列解出来。以是差分其实就是一种反演。
假设原序列是 \(a\)，前缀和数组是 \(A\)，那么可以写出以下这种等式：

• \(A_1 = a_1\)，\(A_2 = a_1 + a_2\)，\(A_3 = a_1 + a_2 + a_3\)
  

考虑把前缀和算子 \(\Delta^{-1}\) 写成矩阵乘法：

\[\begin{bmatrix} A_1 \\ A_2 \\ A_3 \\ A_4 \end{bmatrix} = \begin{bmatrix}  1 & 0 & 0 & 0 \\  1 & 1 & 0 & 0 \\  1 & 1 & 1 & 0 \\  1 & 1 & 1 & 1  \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{bmatrix}\]
考虑把差分算子 \(\Delta\) 写成矩阵乘法：

\[\begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{bmatrix} = \begin{bmatrix}  1 & 0 & 0 & 0 \\  -1 & 1 & 0 & 0 \\  0 & -1 & 1 & 0 \\  0 & 0 & -1 & 1  \end{bmatrix} \begin{bmatrix} A_1 \\ A_2 \\ A_3 \\ A_4 \end{bmatrix}\]
观察这两个矩阵，会发现一个“巧合”，两者是互逆的。
也就是说反演，或者说求差分算子 \(\Delta\)，其实就是求某个矩阵的逆矩阵。也可以认为反演就是容斥。我们后面还会反复用到这种刻画。
加法卷积

我们定义两个序列 \(a\) 和 \(b\) 的加法卷积为：

\[(a * b)_n = \sum_{i+j=n} a_i b_j\]
故可以使用卷积来形貌前缀和、差分的算子：

• 定义 \(I = (1,1,1,1 \dots 1)\) 表示常数函数，那么前缀和 \(A\) 就是 \(a * I\) 做卷积。
  
• 定义 \(D = (1,-1,0,0 \dots 0)\) 表示差分函数，那么差分 \(a\) 就是 \(A * D\) 做卷积。
  
• 定义 \(e = (1, 0,0,0 \dots 0)\) 为单位元函数。类似的，也有 \(I * D = e\) 互逆。
  

这里的常数函数有时也记作 \(\textbf{1}\) 或 \(\textbf{1}(n)\) 的情势。这种做法也可以视作是情势幂级数、生成函数。
高维前缀和 / 高维线性空间

先考虑 2D 的版本，这个也比较众所周知了：
前缀和，意思是，对于两个维度上，都满意下标都小于便是我的位置，它们的值要被加给我：

\[A_{x,y} = \sum_{i \le x} \sum_{j \le y} a_{i,j}\]
这里定义偏序关系是 \(\le\) 即整数的巨细关系。
差分，即容斥，这里的容斥系数容易确定：若下标有 \(c\) 个维度上有减法，系数就是 \((-1)^c\)：

\[a_{x,y} = A_{x,y} - A_{x,y-1} - A_{x-1,y} + A_{x-1,y-1}\]
可以把上式的减一换成别的，这样会容斥出来一个矩形范围。我们后面还会继续提到这点。
求前缀和的时候可以逐维度叠加，这里直接偷 OI wiki 的代码，以三维为例：
[code]  for (int i = 1; i