$Note$-区间修改与查询
作者:
anss
,
2022-07-29 17:08:50
,
所有人可见
,
阅读 169
一、单点修改,区间查询
线段树 $or$ 树状数组 直接维护即可
二、区间修改,单点查询
线段树 $or$ 树状数组 维护原数组的差分数组,区间修改就只需改一个点,然后进行单点查询
1. 推公式转化为单点修改区间查询
$$s_t=\sum_{i=1}^{i=t}d_i×(t+1)-\sum_{i=1}^{i=t}(i×d_i)$$
图片出自
2. 线段树懒标记直接区间修改区间查询
线段树懒标记