「OI」差分表 Difference Table

差分表 (difference table),是一种对数列高度压缩的储存方式。

记得在纪中做过一道差分表的题目。

差分

定义

设数列 \(\{h _ n\}\) 为
$$h _ 0,h _ 1,h _ 2,\cdots,h _ n,\cdots$$

我们定义它的(一阶)差分为
$$\Delta h _ 0,\Delta h _ 1,\Delta h _ 2,\cdots,\Delta h _ n,\cdots$$

其中
$$\Delta h _ n=h _ {n+1}-h _ n$$

对于得到的差分序列,我们可以进一步差分,得到
$$\Delta^2 h _ 0,\Delta^2 h _ 1,\Delta^2 h _ 2,\cdots,\Delta^2 h _ n,\cdots$$

其中
$$\Delta^2 h _ n=\Delta(\Delta h _ n)=\Delta h _ {n+1}-\Delta h _ n$$

更一般地,我们递归定义 \(\{h _ n\}\) 的 \(p\) 阶差分序列为
$$\Delta^p h _ 0,\Delta^p h _ 1,\Delta^p h _ 2,\cdots,\Delta^p h _ n,\cdots$$

其中
$$\Delta^p h _ n=\Delta(\Delta^{p-1} h _ n)$$

特别地,我们有
$$\Delta^0 h _ n=h _ n$$

差分表

定义

我们把数列 \(\{h _ n\}\) 的每个 \(p=0,1,\cdots\) 阶差分序列列成一行得到的一堆在二维平面上的数字称为差分表,例如
$$
\begin{matrix}
&h _ 0&&h _ 1&&h _ 2&&h _ 3&&\cdots\\
&&\Delta h _ 0&&\Delta h _ 1&&\Delta h _ 2&&\cdots\\
&&&\Delta^2 h _ 0&&\Delta^2 h _ 1&&\cdots\\
&&&&\Delta^3 h _ 0&&\cdots\\
&&&&&\cdots\\
\end{matrix}
$$

定理

定理一

设序列的通项是 \(n\) 的 \(p\) 次多项式,即
$$h _ n=a _ pn^p+a _ {p-1}n^{p-1}+\cdots+a _ 1n+a _ 0\quad(n\geq 0)$$
则对于所有的 \(n\geq 0\),\(\Delta^{p+1}h _ n=0\)。


下面我们来证明它。

考虑使用数学归纳法,如果 \(p=0\),那么
$$h _ n=a _ 0$$

那么
$$\Delta h _ n=h _ {n+1}-h _ n=a _ 0-a _ 0=0$$

结论显然成立。

假设 \(p\) 时命题成立,考虑证明 \(p+1\) 时命题也成立。

考虑一阶差分的过程。
$$\Delta h _ n=\sum^p _ {i=0} a _ p(n+1)^p-\sum^p _ {i=0} a _ pn^p$$

那么把式子展开(二项式定理),可以发现 \(n^p\) 在这里面已经被消去,所以一阶差分序列 \(\{\Delta h _ n\}\) 至多是一个 \(n\) 的 \(p-1\) 次多项式,根据归纳假设可以知道这个一阶差分序列的 \(p\) 阶差分全为零,所以对于原来的序列来说,它的 \(p+1\) 阶差分序列全为零,得证。

定理二

差分具有线性性,对于两个序列 \(\{f _ n\}\) 和 \(\{g _ n\}\),我们有
$$\Delta^p(af _ n+bg _ n)=a\Delta^p f _ n+b\Delta^p g _ n$$


显然成立,自己可以算一算。

这个定理用线性代数语言描述,序列的集合形成一个向量空间,而 \(\Delta\) 是这个向量空间上的线性变换。

定理三

差分表可以由最左边的那一条斜线上的元素唯一确定。
最左边的斜线指的是
$$h _ 0,\Delta h _ 0,\Delta^2 h _ 0,\cdots$$


考虑一个简单的事情,从 \(\Delta^{0\sim p}h _ 0\),我们可以得到 \(h _ {0\sim p}\)。

  • 首先,由 \(\Delta^p h _ 0\) 和 \(\Delta^{p-1} h _ 0\) 可以得到 \(\Delta^{p-1} h _ 1\)。
  • 然后根据 \(\Delta^{p-1} h _ {0\sim 1}\) 和 \(\Delta^{p-2} h _ 0\) 可以得到 \(\Delta^{p-2} h _ {1\sim 2}\)。
  • 然后递推很多步。
  • 最终我们可以得到 \(\Delta^0 h _ {0\sim p}\),也就是 \(h _ {0\sim p}\)。

定理四

设 \(\{h _ n\}\) 的差分表的最左边的斜线为 \(c _ 0,c _ 1,c _ 2,\cdots,c _ p,0,0,\cdots\),其中 \(c _ p\) 不为零。
那么我们有
$$h _ n=c _ 0\binom{n}{0}+c _ 1\binom{n}{1}+c _ 2\binom{n}{2}+\cdots+c _ p\binom{n}{p}$$

仿照定理三的证明显然。

应用

考虑快速求和 \(p\) 阶多项式数列 \(\{h _ n\}\)。
$$\sum^k _ {i=0}h _ i$$

我们求出差分表最左边斜线元素,记为 \(c _ 0,c _ 1,c _ 2,\cdots,c _ p\),时间复杂度为 \(\Theta(p\alpha(n)+p^2)\),其中 \(\alpha(n)\) 为单次求 \(h _ n\) 的时间复杂度,实际上 \(\alpha(n)\) 最优为 \(\Theta(p)\)。

然后推式子
$$
\begin{aligned}
\sum^k _ {i=0}h _ i&=\sum^k _ {i=0}(c _ 0\binom{i}{0}+c _ 1\binom{i}{1}+\cdots+c _ p\binom{i}{p})\\
&=\sum^k _ {i=0}c _ 0\binom{i}{0}+\sum^k _ {i=0}c _ 1\binom{i}{1}+\cdots+\sum^k _ {i=0}c _ p\binom{i}{p}\\
&=c _ 0\sum^k _ {i=0}\binom{i}{0}+c _ 1\sum^k _ {i=0}\binom{i}{1}+\cdots+c _ p\sum^k _ {i=0}\binom{i}{p}\\
\end{aligned}
$$

我们又有
$$\sum^n _ {k=0}\binom{k}{p}=\binom{n+1}{p+1}$$

所以
$$
\begin{aligned}
\sum^k _ {i=0}h _ i&=c _ 0\sum^k _ {i=0}\binom{i}{0}+c _ 1\sum^k _ {i=0}\binom{i}{1}+\cdots+c _ p\sum^k _ {i=0}\binom{i}{p}\\
&=c _ 0\binom{k+1}{1}+c _ 1\binom{k+1}{2}+\cdots+c _ p\binom{k+1}{p+1}\\
&=\sum^p _ {i=0}c _ i\binom{k+1}{i+1}
\end{aligned}
$$

这种利用差分表的求和方法的时间复杂度为 \(\Theta(p^2)\),预处理时间复杂度也为 \(\Theta(p^2)\),比朴素的 \(\Theta(kp)\) 算法不知道快了多少倍。