Segment Tree

O(log n) per query

Point updates and range queries over any associative operation (min, max, sum, gcd, ...). This is the compact iterative (bottom-up) version, with O(n) construction from an initial array. Swap the combine lines to change the operation. Reach for it when a Fenwick tree isn't enough (min/max, non-invertible operations).

// use it on

CSES: Dynamic Range Minimum Queries ↗

Point assignments mixed with range-minimum queries. Replace the + combine with min and it's done.

// the code

struct SegTree {  // point update, range query on [l, r)
    int n;
    vector<long long> t;
    SegTree(int n) : n(n), t(2 * n, 0) {}
    SegTree(const vector<long long>& a) : n(a.size()), t(2 * a.size()) {
        copy(a.begin(), a.end(), t.begin() + n);
        for (int i = n - 1; i > 0; i--)
            t[i] = t[2 * i] + t[2 * i + 1];  // combine
    }
    void update(int i, long long v) {  // set a[i] = v
        for (t[i += n] = v; i > 1; i >>= 1)
            t[i >> 1] = t[i] + t[i ^ 1];  // combine
    }
    long long query(int l, int r) {  // fold over [l, r)
        long long res = 0;  // identity of the combine
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res += t[l++];
            if (r & 1) res += t[--r];
        }
        return res;
    }
};

// more range queries

Lazy Segment Tree Fenwick Tree (BIT)Sparse Table