带 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)$ 为无效结点。这些结点的维护信息不能影响到有效结点。比如维护区间的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)即可

模板

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);
}