声明由于博主已经ICPC退役且本人非数学/计算机科班在此浅浅分享一下个人的粗浅理解。若有不同想法欢迎在讨论区共同探讨学习。提及差分就不得不提及前缀和。他们像孪生兄弟一样捆绑到了一起互为逆运算。不难发现前缀和与差分实际上就是离散版的微积分。那么在微积分中我们学习了ODE常微分方程自然也就会有PDE偏微分方程、积分方程、差分方程等。差分方程在经济学、商学中具有重要研究价值通常会用于预测经济模型。一维差分很好理解二维差分却是让每个人都头痛过的问题。下面博主就谈及本人对二维差分的粗浅理解。一维里差分算子是Δxnxn1−xn\Delta x_n x_{n1}-x_nΔxn​xn1​−xn​它刻画的是沿x轴方向上的变化二维里差分不是一个数而是一组方向上的差分自然就有两个基本差分算子x 方向差分横向Δxf(i,j)f(i1,j)−f(i,j)\Delta_x f(i,j)f(i1,j)-f(i,j)Δx​f(i,j)f(i1,j)−f(i,j)y 方向差分纵向Δyf(i,j)f(i,j1)−f(i,j)\Delta_y f(i,j)f(i,j1)-f(i,j)Δy​f(i,j)f(i,j1)−f(i,j)这对应连续版中的偏导Δx↔∂∂x,Δy↔∂∂y\Delta_x \leftrightarrow \frac{\partial}{\partial x},\quad \Delta_y \leftrightarrow \frac{\partial}{\partial y}Δx​↔∂x∂​,Δy​↔∂y∂​。它第一次把差分从一条线给推到了一个面上。它们回答的问题是沿着 x 和 y 轴独立的走一步值分别变了多少。厘清了单个方向上的差分那么我们下面将探讨二阶混合差分这一部分对应的连续版本即为二阶混合偏导。数学上它写作ΔxΔyf(i,j)\Delta_x\Delta_y f(i,j)Δx​Δy​f(i,j)逐层展开Δyf(i,j)f(i,j1)−f(i,j)Δx(Δyf)(i,j)(f(i1,j1)−f(i1,j))−(f(i,j1)−f(i,j)) f(i1,j1)−f(i1,j)−f(i,j1)f(i,j)\begin{aligned} \Delta_y f(i,j) f(i,j1)-f(i,j) \\ \Delta_x(\Delta_y f)(i,j) (f(i1,j1)-f(i1,j))-(f(i,j1)-f(i,j)) \ f(i1,j1)-f(i1,j)-f(i,j1)f(i,j) \end{aligned}Δy​f(i,j)Δx​(Δy​f)(i,j)​f(i,j1)−f(i,j)(f(i1,j1)−f(i1,j))−(f(i,j1)−f(i,j))​f(i1,j1)−f(i1,j)−f(i,j1)f(i,j)​这正式我们在ICPC中用的滚瓜烂熟的二维差分公式g(i,j)f(i,j)−f(i−1,j)−f(i,j−1)f(i−1,j−1)g(i,j) f(i,j)- f(i-1,j)-f(i,j-1) f(i-1,j-1)g(i,j)f(i,j)−f(i−1,j)−f(i,j−1)f(i−1,j−1)它不是在看斜率而是在看离散的曲率也就是弯曲程度。实际上其对应的就是连续版中的二阶混合偏导∂2f∂x,∂y\dfrac{\partial^2 f}{\partial x,\partial y}∂x,∂y∂2f​。那么为什么二维前缀和为什么能还原原数组呢我们回顾一下二维差分的定义式Di,jAi,j−Ai−1,j−Ai,j−1Ai−1,j−1D_{i,j}A_{i,j}-A_{i-1,j}-A_{i,j-1}A_{i-1,j-1}Di,j​Ai,j​−Ai−1,j​−Ai,j−1​Ai−1,j−1​那么反过来原数组 (A_{i,j}) 可以由 (D) 的二维前缀和得到Ai,j∑x1i∑y1jDx,yA_{i,j}\sum_{x1}^{i}\sum_{y1}^{j}D_{x,y}Ai,j​∑x1i​∑y1j​Dx,y​其实这就是对差分数组在做前缀和。这一步对应的连续版为二重积分A(x,y)∫∫∂2A∂x∂y,dx,dyA(x,y)\int\int \frac{\partial^2 A}{\partial x\partial y},dx,dyA(x,y)∫∫∂x∂y∂2A​,dx,dy所以二维差分的连续版本就是二维混合偏导二维前缀和的连续版本就是二重积分。