二阶差分（区间加等差数列）

公式推导过程

设 $a$ 是原数组，$b$ 是一阶差分数组，$c$ 是二阶差分数组。

$b$ 的定义：$b_i=\begin{cases}a_i-a_{i-1}&i>1\\a_1&i=1\end{cases}$

$c$ 的定义：$c_i=\begin{cases}b_i-b_{i-1}&i>1\\b_1&i=1\end{cases}$

考虑在区间 $[l,r]$ 内对原数组加上首项为 $s$，公差为 $d$，末项 $t=s+(r-l)d$ 的等差数列对 $a$ 的影响：

$a'_x\gets \color{#6faaff}a_x+s+(x-l)d$，（$x\in[l,r]$）

考虑 $a$ 的变化对 $b$ 的影响：

$b'_l\gets a'_l-a_{l-1}\gets a_{l-1}+b_l+s+(l-l)d-a_{l-1}\gets \color{#6faaff}b_l+s$

$b'_x\gets a'_x-a'_{x-1}\gets a_{x-1}+b_x+s+(x-l)d-[a_{x-1}+s+(x-1-l)d]\gets \color{#6faaff}b_x+d$，

（$x\in[l+1,r]$）

$b'_{r+1}\gets a_{r+1}-a'_r\gets a_r+b_{r+1}-[a_r+s+(r-l)d]\gets \color{#6faaff}b_{r+1}-t$

考虑 $b$ 的变化对 $c$ 的影响：

$c'_l\gets b'_l-b_{l-1}\gets b_{l-1}+c_l+s-b_{l-1}\gets \color{#6faaff}c_l+s$

$c'_{l+1}\gets b'_{l+1}-b'_l\gets b_l+c_{l+1}+d-(b_l+s)\gets\color{#6faaff}c_{l+1}+d-s$

$c'_x\gets b'_x-b'_{x-1}\gets b_{x-1}+c_x+d-(b_{x-1}+d)\gets\color{#6faaff}c_x$，（$x\in[l+2,r]$）

（重要的发现：$c_x$ 保持不变）

$c'_{r+1}\gets b'_{r+1}-b'_r\gets b_r+c_{r+1}-t-(b_r+d)\gets\color{#6faaff}c_{r+1}-t-d$

$c'_{r+2}\gets b_{r+2}-b'_{r+1}\gets b_{r+1}+c_{r+2}-(b_{r+1}-t)\gets\color{#6faaff}c_{r+2}+t$

每次操作都只会改变 $c$ 上 $4$ 个位置的值，因此可以 $O(1)$ 时间实现区间加等差数列。

如何得到原数组

根据定义，

$$\because c_i=\begin{cases}b_i-b_{i-1}&i>1\\b_1&i=1\end{cases}$$

$$\therefore b_i=\sum_{j=1}^ic_j$$

$$\because b_i=\begin{cases}a_i-a_{i-1}&i>1\\a_1&i=1\end{cases}$$

$$\therefore a_i=\sum_{j=1}^ib_j=\sum_{j=1}^i\sum_{k=1}^jc_k$$

代码示例

// 在区间 [l,r] 加上首项为 s, 公差为 d 的等差数列
void add(int l, int r, int s, int d) {
    int t = s + (r - l) * d;
    c[l] += s;
    c[l + 1] += d - s;
    c[r + 1] -= t + d;
    c[r + 2] += t;
}
int ask(int k) { // 查询 a_k 的值
    int a = 0, b = 0;
    for(int i = 1; i <= k; i++)
        a += (b += c[i]);
    return a;
}