> 生产队的驴在集训营也要生产。本文完成
> 前情提要:树状数组(1)
前言
为啥要区间修改和单点查询啊。
线段树真好玩,嘿嘿。
(被 RE 扇飞了)
滚回来写树状数组。
正文
前文回顾
上一文章我们讲解了单点修改和前缀和查询的树状数组。
前置知识 - 差分
差分数组的每一项代表原数组这一项和前一项的差,即:
注意到由于差分数组是原数组两项之间的差,通过对差分数组做前缀和可以得到原数组。
差分数组方便进行区间修改,如果要对 [l,r][l,r][l,r] 区间加上 kkk,只需要对 dld_ldl 加上 kkk 然后对 dr+1d_{r+1}dr+1 减去 kkk 即可,即:
区间修改和单点查询的树状数组
注意到树状数组的核心是前缀和。
如果我们让树状数组维护差分数组,那么由于查询操作是一个前缀和,可以将查询的结果从查询前缀和转为查询下标的当前值。
同时将修改操作改为标准的差分操作即可,注意建树也要进行修改。
注意到只有少量修改。
例题
P3368 【模板】树状数组 2 / A22467.【模板】树状数组 2
标准的区间修改单点查询。
下期预告
也许会有下期?