设 a_i 表示原数组，b_i 表示所有长度为 i 的区间的权值和。首先我们对于一对 (i,j) 求出 a_i 对 b_j 的贡献（点对点）。发现这实际上就是求有多少个长度为 j 的区间覆盖了位置 i，讨论左端点的范围可以得出下式：
b_j\gets a_i\times [\min(i,n-j+1)-\max(1,i-j+1)+1]
如果把这个贡献看成关于 j 的函数，那么它应该由三段直线组成，这些直线的斜率依次为 a_i,0,-a_i，两个拐点分别在 \min 和 \max 中两项相等时取到。假设我们要单点修改 a_i，则应该对 b 数组加上这个函数，这用二阶差分就能维护，即
\left\{\begin{array}{l}
\Delta^2 b_1=1\\
\Delta^2 b_{i+1}=-1\\
\Delta^2 b_{n-i+2}=-1
\end{array}\right.
现在考虑区间修改，对于一次将 [l,r] 加上 x 的操作，考虑将其拆成「将 [l,n] 加上 x」和「将 [r+1,n] 减去 x」这两部分。我们现在需要知道的，就是对于一个位置 i，所有 i\leq j\leq n 的 a_j 对 b 数组的贡献和。直接将上面的二阶差分相加，可以得到
\left\{\begin{array}{l}
\Delta^2 b_1=n-i+1\\
\Delta^2 b_{i+1},\Delta^2 b_{i+2},\cdots,\Delta^2 b_{n+1}=-1\\
\Delta^2 b_{n-i+2},\Delta^2 b_{n-i+1},\cdots,\Delta^2 b_{2}=-1
\end{array}\right.
又出现了区间加减一个常数的形式，不难想到在二阶差分上再次差分，也就是对 b 数组的三阶差分修改：
\left\{\begin{array}{l}
\Delta^3 b_1=n-i+1\\
\Delta^3 b_2=i-n-2\\
\Delta^3 b_{i+1}=-1\\
\Delta^3 b_{n-i+3}=1
\end{array}\right.
那么现在问题已经转化为一个一般的模型了：单点修改，维护 k 次前缀和。因为原题中要求 b_l\sim b_r 之和，所以外层还要套一个前缀和，因此这里 k=4。我们可以通过一些数学推导来解决这个 k 一般时的问题。
对于一个数组 a_i，记它的 \text{OGF} 为 A(x)。那么它的 k 阶前缀和为 \dfrac{A(x)}{(1-x)^k}。根据广义二项式定理，有
\begin{aligned}
(1-x)^{-k}
&=\sum_{i=0}^{+\infty}\binom{-k}{i}(-x)^i\\
&=\sum_{i=0}^{+\infty}(-1)^i\binom{i+k-1}{i}(-x)^i\\
&=\sum_{i=0}^{+\infty}\binom{i+k-1}{i}x^i
\end{aligned}
所以 \Sigma^{k}a_i=\sum_{j=0}^{i}\binom{j+k-1}{j}a_{i-j}。当然我们不能直接用这个式子暴力去算，考虑 a_i 对 a_{i+j} 的贡献，设
F(x)=\binom{x+k-1}{x}=\dfrac{(x+k-1)^{\underline{k-1}}}{(k-1)!}
则贡献为 a_i\times F(j)。发现 F(j) 是关于 j 的 k-1 次多项式，这个贡献可能是可以叠加的，但 j 依赖于与 i 的相对位置关系，处理起来十分不方便，我们希望得到一个绝对位置的表达。设同样为 k-1 次的多项式 F_*(x) 满足 F_*(i+j)=F(j)，那么这次修改对 \Sigma^k a_p 产生的贡献就是 F_*(p)，将对应次项的系数叠加上去就行了。有一个要注意的地方就是不能贡献到小于 i 的位置，因为首先这不符合前缀和的定义，其次这些位置的点值是没有意义的，加上去就会出错。所以需要使用树状数组维护区间加以及单点查询。
现在只需要求出 F_* 就可以了。我们知道 F_*(x) 实际上就是将 F(x) 水平平移得到的，考虑 F(x+c) 的式子：
\begin{aligned}
F(x+c)&=
\sum_{i=0}^{k-1}f_i(x+c)^i\\
&=\sum_{i=0}^{k-1}f_i\sum_{j=0}^{i}\binom{i}{j}x^jc^{i-j}\\
&=\sum_{j=0}^{k-1}x^j\sum_{i=j}^{k-1}f_i\binom{i}{j}c^{i-j}
\end{aligned}
直接 O(k^2) 计算平移每种长度得到的多项式系数即可。本题预处理复杂度为 O(nk^2)，单次修改和查询的复杂度都是 O(k\log n) 的。
冷滟泽的个人博客