区间修改线段树能在 $O(logn)$ 的时间内完成区间查询或区间修改操作,实现方式是通过给结点打lazy
标记。操作一般由以下几个函数构成:
void init()
:建树void flag(int k)
:修改或添加结点 $k$ 的标记void maintain(int k)
:根据结点 $k$ 的子树及其自身的标记计算它维护的值void push_down(int K)
:将结点 $k$ 的标记下传void update(...)
:递归地维护整个线段树void query(...)
:递归地查询整个线段树
注意点
对于建树,首先需要找到一个最小的正整数 $n’$,满足:$n’ >= n$ 和 $n’$ 为 $2 $ 的幂。于是 $n’ 2 - 1$ 即为整个线段树的结点数量。其中 $1$ 号结点为
root
,$[1, n’)$ 为非叶子结点,$[n’, n’ 2)$ 为叶子结点。
实际有效的叶子结点的下标在 $[n’, n’ + n)$ 中,$[n’ + n, n’ * 2)$ 为无效结点。这些结点的维护信息不能影响到有效结点。比如维护区间的sum
,min
,max
时,无效结点应该置其sumv = 0
,maxv = -INF
,minv = INF
。建树时间复杂度 $O(n)$。仅在
flag()
和push_down()
操作中可以对结点的标记进行修改。如果是双标记或者是多标记线段树,则所有标记都需要考虑在内。push_down()
操作还需要考虑两个子树。仅在
maintain()
中更新结点维护的值(比如sumv
,maxv
,minv
等),维护的信息必须要能在 $O(1)$ 或者 $O(log)$ 的时间内维护完成,否则更新操作将会严重拖慢效率。要求先将旧值清零,再根据左右子树的维护的值和自身的标记来更新自身维护的值。对于
update()
和query()
操作,其维护的区间从 0 开始还是从 1 开始并不重要,但root
结点必须为 $1$ 号点,query
操作同理。对于update(k, l, r, a, b, v)
:- 若给出的区间 $[a, b]$ 从 0 开始,则调用
update(1, 0, n' - 1, a, b ,v)
即可 - 若给出的区间 $[a, b]$ 从 1 开始,则调用
update(1, 1, n', a, b ,v)
即可
- 若给出的区间 $[a, b]$ 从 0 开始,则调用
模板
struct node { |