区间修改

一句话理解

区间修改用差分只需 O(1) 更新。

为什么要学

n 次区间加，暴力是 O(n²)，差分是 O(n)。

讲解

先把所有修改打到 d 上，最后一次扫描还原。若修改和查询穿插，差分不够，要树状数组。

例子

100 次把 [1,n] 加 1，暴力 100n，差分每次两步。

常见错误

• 有中间查询还只用差分数组不还原。
• k 为负时符号写反。