「学习笔记」浅谈离散微积分

微积分是数学分析中的有力工具，其核心是微分和积分，类比微积分中的一整套系统，《具体数学》中引入了一套研究差分和求和的工具——离散微积分 (discrete calculus)

回顾微积分

在微积分中，我们有微分算子 (differential operator) $$

若有 $$ 则称 $$ 是 $$ 的原函数

微积分的核心：牛顿 - 莱布尼茨公式 (Newton - Leibniz formula) $$

定义与记号

类比微分算子，定义差分算子 $$

类似地，若 $$ 则称 $$ 是 $$ 的原函数，不难发现 $$

于是类比定积分，定义和式 $$

类比不定积分，有不定和式 $$ 其中 $$ 为常数

至此，我们类比定义了离散情况下的微分、积分和牛顿 - 莱布尼茨公式

从定义开始完善系统

仅靠定义和牛顿 - 莱布尼茨公式构建不起微积分的大厦，同样的，刚才定义的记号也无法帮助我们快速计算和式，我们需要进一步探究它的性质

首先，根据定义显然有差分算子对于加法、减法的分配率成立

幂法则

先从微积分中最简单的幂法则说起，寻找它的替代品

在微积分中，有 $$ 但显然 $$，但是我们有一种类似幂的数学工具：下降幂

定义下降幂 $$

发现 $$

同样的，在 $$ 时，有不定和式 $$

类似 $$，$$ 时，有 $$，其中 $$ 为调和级数前 $$ 项和，不难发现 $$ 时 $$ 其中 $$ 为 欧拉 - 马歇罗尼常数，这一点也印证了离散微积分和微积分密不可分的联系

例题：

求和 $$

首先有 $$

考虑求出原函数 $$

于是有 $$

在 OI 中，我们可以将多项式转换为下降幂多项式，从而在 $$ 时间内求出 $$ 次多项式的值的前缀和

至此，我们探究出了多项式的差分、求和并探寻了离散微积分在处理求和上的初步应用

指数函数

在微积分中，以 $$ 为底的指数函数 $$ 拥有良好的性质：$$ 和 $$ 那么在离散微积分中是否也有具备这种性质的函数呢？

答案是有的：$$

不难发现 $$ 和 $$

在微积分中，对于任意底数的指数函数 $$ 有 $$ 和 $$

首先 $$ 的差分显然是 $$

考虑 $$ 的不定和式，不妨设 $$，两边求差分得 $$，于是 $$

积法则

定义平移算子 $$

不难发现

$$

更为简单的表示为：$$

分部求和

在微积分中有分部积分公式：$$

这一公式是对微分的积法则移项后左右积分得到的

同理也可以得到分部求和的公式：

$$

例题与应用

求和 $$

先求原函数，考虑带入 $$: $$

于是有： $$

求和 $$

先求原函数，考虑带入 $$: $$

对于后一项继续分部求和，带入 $$:

$$

带回上式： $$

求和： $$

HEOI/TJOI 2016 求和：洛谷 LOJ

求和 $$

首先进行变形： $$

其中 $$，特别地 $$

考虑用离散微积分简化后一个和式，于是求原函数，考虑带入$$： $$

另外有： $$

于是对于每一个 $$ 递推出它的原函数在 $$ 和 $$ 处的值，相减即可

用线性筛筛出 $$ 即可在 $$ 时间内得到答案

完。