← all categories

Segment Tree Dynamic Lazy eba76cf2

Dynamic (sparsely allocated) segment tree over an implicit range, e.g. [0, 1e9]. Nodes are created only along touched paths, so no initial array is needed and no coordinate compression is required. Range add + range sum; T needs operator+ and a default-constructed zero.

Time: O(\log(\text{range})) per operation; O(q \log(\text{range})) nodes total. tested

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

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

    long long lo, hi;
    Node *root = new Node();

    DynamicSegmentTree(long long lo, long long hi) : lo(lo), hi(hi) {}

    void push(Node *n, long long l, long long r) {
        if (!n->left) { n->left = new Node(); n->right = new Node(); }
        if (n->lazy != T()) {
            long long m = (l + r) / 2;
            n->left->val += n->lazy * (m - l + 1);
            n->left->lazy += n->lazy;
            n->right->val += n->lazy * (r - m);
            n->right->lazy += n->lazy;
            n->lazy = T();
        }
    }

    void update(long long ul, long long ur, T v, Node *n = nullptr, long long l = -1, long long r = -1) {
        if (!n) { n = root; l = lo; r = hi; }
        if (ur < l || r < ul) return;
        if (ul <= l && r <= ur) { n->val += v * (r - l + 1); n->lazy += v; return; }
        push(n, l, r);
        long long m = (l + r) / 2;
        update(ul, ur, v, n->left, l, m);
        update(ul, ur, v, n->right, m + 1, r);
        n->val = n->left->val + n->right->val;
    }

    T query(long long ql, long long qr, Node *n = nullptr, long long l = -1, long long r = -1) {
        if (!n) { n = root; l = lo; r = hi; }
        if (qr < l || r < ql) return T();
        if (ql <= l && r <= qr) return n->val;
        push(n, l, r);
        long long m = (l + r) / 2;
        return query(ql, qr, n->left, l, m) + query(ql, qr, n->right, m + 1, r);
    }
};