← all categories

Segment Tree Iterative cee7ab5d

Iterative point-update segment tree, no recursion, no lazy propagation. Default op is max; edit comb()/ID for a different associative op.

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

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

template <typename T>
struct SegmentTree {
    int n;
    vector<T> tree;
    T ID = numeric_limits<T>::lowest();  // identity for comb()

    T comb(T a, T b) { return max(a, b); }  // op: edit for a different associative op

    SegmentTree(vector<T> &a) : n(a.size()), tree(2 * n) {
        for (int i = 0; i < n; i++) tree[i + n] = a[i];
        for (int i = n - 1; i > 0; i--) tree[i] = comb(tree[2 * i], tree[2 * i + 1]);
    }

    void update(int i, T v) {
        tree[i += n] = v;
        for (i >>= 1; i > 0; i >>= 1) tree[i] = comb(tree[2 * i], tree[2 * i + 1]);
    }

    T query(int l, int r) {  // inclusive [l, r]
        T res = ID;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = comb(res, tree[l++]);
            if (r & 1) res = comb(res, tree[--r]);
        }
        return res;
    }
};