带 lazy 标记的区间修改线段树

区间修改线段树能在 $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)$ 为无效结点。这些结点的维护信息不能影响到有效结点。比如维护区间的summinmax时,无效结点应该置其sumv = 0maxv = -INFminv = 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)即可

模板

segment-tree.cppview raw
struct node {
ll setv, sumv;
node(): sumv(0), setv(-INF) {}
};

int n, m, _n;
node* tree;

void init() {
_n = 1;
while (_n < n) _n <<= 1;
tree = new node[_n << 1];
for (int i = _n; i < _n + n; i++) {/*read tree[i]*/}
for (int p = _n >> 1; p; p >>= 1)
for (int i = p; i < (p << 1); i++) {
int lt = i << 1, rt = (i << 1) + 1;
//tree[i].sumv = tree[lt].sumv + tree[rt].sumv;
}
}

inline void maintain(int k, int l, int r) {}

inline void push_down(int k) {}

inline void flag(int k, int v) {}

inline void update(int k, int l, int r, int a, int b, int v) {
int lt = k << 1, rt = (k << 1) + 1;
if (a <= l && r <= b)
flag(k, v);
else {
push_down(k);
int mid = (l + r) >> 1;
if (a <= mid) update(lt, l, mid, a, b, v);
else maintain(lt, l, mid);
if (mid < b) update(rt, mid + 1, r, a, b, v);
else maintain(rt, mid + 1, r);
}
maintain(k, l, r);
}

inline int query(int k, int l, int r, int a, int b) {
if (r < a || l > b) return 0;//or INF, -INF
//if flag...(e.g. setv)
if (a <= l && r <= b) {}
int mid = (r + l) >> 1, lt = k << 1, rt = (k << 1) + 1;
return query(lt, l, mid, ans) + query(rt, mid + 1, r, ans);
}