← all categories

Segment Tree Lazy 1c016c3d

Recursive segment tree, eager array build, range update with lazy propagation. Default op is range-add + range-min; edit comb()/apply() for another op (see treap-implicit.h for the op-block pattern this follows). T needs operator+, a zero, and to be comparable with numeric_limits.

Time: O(\log n) per operation. tested

content/data-structures/segment-tree-lazy.h

template <typename T>
struct LazySegmentTree {
    struct Node {
        int l, r;
        T val, lazy = T();
        Node *left = nullptr, *right = nullptr;
    };

    T ID() { return numeric_limits<T>::max(); }              // op: identity for comb()
    T comb(T a, T b) { return min(a, b); }                    // op: combine two children
    void apply(Node *n, T v) { n->val += v; n->lazy += v; }   // op: push a lazy tag onto a node

    Node *root;

    LazySegmentTree(vector<T> &a) { root = build(0, (int)a.size() - 1, a); }

    Node *build(int l, int r, vector<T> &a) {
        Node *n = new Node();
        n->l = l; n->r = r;
        if (l == r) { n->val = a[l]; return n; }
        int m = (l + r) / 2;
        n->left = build(l, m, a);
        n->right = build(m + 1, r, a);
        n->val = comb(n->left->val, n->right->val);
        return n;
    }

    void push(Node *n) {
        if (n->lazy != T()) {
            if (n->left) { apply(n->left, n->lazy); apply(n->right, n->lazy); }
            n->lazy = T();
        }
    }

    void update(int ul, int ur, T v, Node *n = nullptr) {
        if (!n) n = root;
        if (ur < n->l || n->r < ul) return;
        if (ul <= n->l && n->r <= ur) { apply(n, v); return; }
        push(n);
        update(ul, ur, v, n->left);
        update(ul, ur, v, n->right);
        n->val = comb(n->left->val, n->right->val);
    }

    T query(int ql, int qr, Node *n = nullptr) {
        if (!n) n = root;
        if (qr < n->l || n->r < ql) return ID();
        if (ql <= n->l && n->r <= qr) return n->val;
        push(n);
        return comb(query(ql, qr, n->left), query(ql, qr, n->right));
    }
};