差分还原

一句话理解

差分还原就是对 d 做一次前缀和。

为什么要学

修改结束后才能得到真正的数组。

讲解

a[1]=d[1]，a[i]=a[i-1]+d[i]。不要还原两次。

还原后 d 和 a 的关系要想清楚，别用错数组。

例子

for (int i = 1; i <= n; i++) a[i] = a[i - 1] + d[i];

前缀和还原原数组。

常见错误

• 还原时从 0 开始却 d[0] 无意义。
• 边还原边继续用差分公式。