P1438 无聊的数列 分析

__ryp__ · 2023-12-21 15:10:00 · 个人记录

本题的特点是每个点上要加的值是不一样的，但是差值之间是一样的。

这让我们想到差分。

事实上，我们可以对这个序列进行差分。这样，点 p 的值就是 \sum\limits_{i=1}^p d_i。这恰好就是线段树所可实现的区间更改和区间查询。

更新区间 [l, r] 时，我们需要将 l 点加上 k，将 [l+1, r] 上每个点加上公差 d，最终在 r + 1 点处减去 a_{r - l + 1}，即 k + d\times (r - l)。