iv. Segment Tree

A segment tree stores an associative aggregate for each of the $O(n)$ canonical segments. Any range splits into $O(\log n)$ of them. All the power is in what a node stores: if two adjacent segments’ summaries can be combined into the summary of their union, a segment tree answers range queries over it.

Bottom-up monoid tree (AtCoder style)

template<class S, S (*op)(S, S), S (*e)()> struct SegTree {
    int n, size; vector<S> t;
    SegTree(const vector<S>& a) : n(sz(a)), size(1) {
        while (size < n) size <<= 1;
        t.assign(2 * size, e());
        copy(all(a), t.begin() + size);
        for (int i = size - 1; i > 0; i--) t[i] = op(t[2 * i], t[2 * i + 1]);
    }
    void set(int p, S v) { for (t[p += size] = v; p >>= 1; ) t[p] = op(t[2 * p], t[2 * p + 1]); }
    S get(int p) const { return t[p + size]; }
    S prod(int l, int r) const {                       // [l, r), keeps left-to-right order
        S sl = e(), sr = e();
        for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
            if (l & 1) sl = op(sl, t[l++]);
            if (r & 1) sr = op(t[--r], sr);
        }
        return op(sl, sr);
    }
    template<class F> int maxRight(int l, F f) const { // largest r with f(prod(l, r)) true; f(e()) must be true
        if (l == n) return n;
        l += size; S acc = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(acc, t[l]))) {
                while (l < size) { l = 2 * l; if (f(op(acc, t[l]))) acc = op(acc, t[l++]); }
                return l - size;
            }
            acc = op(acc, t[l++]);
        } while ((l & -l) != l);
        return n;
    }
    template<class F> int minLeft(int r, F f) const {  // smallest l with f(prod(l, r)) true
        if (r == 0) return 0;
        r += size; S acc = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(t[r], acc))) {
                while (r < size) { r = 2 * r + 1; if (f(op(t[r], acc))) acc = op(t[r--], acc); }
                return r + 1 - size;
            }
            acc = op(t[r], acc);
        } while ((r & -r) != r);
        return 0;
    }
};

• op only needs to be associative. The left and right partial results are kept apart, so non-commutative monoids (matrices, function composition, strings) work.
• maxRight / minLeft are binary searches on the tree in $O(\log n)$: “first position where the prefix sum from $l$ exceeds $k$”, “longest segment starting at $l$ with gcd $>1$”, “nearest element to the left that is $\ge x$” (with max).
• It’s about 2x faster than a recursive tree and uses $2\cdot 2^{\lceil \log n\rceil }$ nodes.

Proof: the bottom-up tree is correct

Layout. Leaves occupy $t[\text{size}..\text{size}+n)$ (position $p$ at index $p+\text{size}$), and each internal node $i\ge 1$ covers exactly the leaves under it in the complete binary tree with children $2i,2i+1$ — the build’s bottom-up loop computes this bottom-up so every $t[i]=op$ of its two children is established before it’s used as a child higher up. set walks from a leaf to the root re-deriving each ancestor from its (now up-to-date) children, so every node on the path is correct after the call, and every node off the path was untouched and still correct. prod(l,r): this is the standard “iterative segment tree range query” — walking $l,r$ upward while peeling off a node whenever it is the right (resp. left) child of its parent and therefore wholly inside $[l,r)$ without its sibling being needed yet. Each peeled node’s range is disjoint from every other peeled node’s range (they’re peeled in strictly shrinking, non-overlapping chunks moving inward from both ends), their union is exactly $[l,r)$ (by induction: before peeling, $[l,r)$ in leaf coordinates is exactly covered by the current $[l,r)$ in node-index coordinates read as “all leaves under nodes $l..r-1$ at the current level”), and sl/sr accumulate them in left-to-right order (left-peeled nodes appended to sl in increasing order, right-peeled nodes prepended to sr), so op(sl, sr) folds $[l,r)$ in the correct order even for non-commutative op. maxRight/minLeft perform binary search over this same canonical decomposition: they walk the same peeling order as prod(l, n) (resp. prod(0, r)) would, but stop and descend into a block as soon as including it whole would violate f, then binary-search inside that one block top-down — correct because f is required to be monotone on prefixes starting at $l$ (an implicit precondition, matching the AtCoder Library contract), so the first failing block is uniquely identified by this walk and the descent inside it finds the exact boundary. $■$

Tested against brute force (accumulate for prod; linear prefix scans for maxRight/minLeft) over random arrays, random point sets, and random queries — all match.

A recursive tree is easier to extend with lazy propagation, dynamic nodes and custom descents; see Lazy Propagation.

Node design

Query	Node stores	Merge
max subarray sum in a range	sum, best prefix, best suffix, best	see Kadane
min and how many times it occurs	(min, count)	add counts on ties
longest run of equal values / of ones	length, prefix run, suffix run, best, end values	join runs across the middle
balanced bracket subsequence length	(matched, open, close)	m = min(L.open, R.close)
is the range a valid bracket sequence	(sum, min prefix)	prefix min of the right part shifted by the left sum
range of a linear recurrence / DP transition	a matrix	matrix product (order matters)
composition of functions $x\to ax+b$	$(a,b)$	composition
palindrome check of a substring with updates	forward and backward polynomial hash	shift and add
number of inversions in a range of a permutation (static)	merge sort tree or wavelet
”LIS-like” or “visible from the left” counts	max and the answer with a $O(\log )$ helper descent	”$O({\log }^2)$ pull” segment tree (the classic visible-buildings problem)
distinct values count	not mergeable: offline sweep or persistence
mode / majority	Boyer-Moore pair (candidate, count)	candidate survives with count difference

$O({\log }^{2}n)$ pull technique: when the merge needs a query into the right child (“count prefix maxima in the right child that exceed the left child’s max”), implement it as a descent of the right child that is $O(\log n)$. Then updates cost $O({\log }^{2}n)$. Classic for “number of visible buildings with point updates”.

Other forms

• Segment tree over values (counts per value): $k$-th smallest, rank, and “sum of the $k$ smallest” by descent; with compression or as a dynamic tree over $[0,10^9]$.
• Segment tree on a trie of indices (XOR on indices): to apply $i\to i\oplus x$ to all positions and query sums, note that XOR with bit $b$ swaps the two children at the level of bit $b$. Keep a lazy XOR mask per node and swap children when the mask has the level’s bit. A cheaper offline trick: precompute, for every node and every mask of its levels, the aggregate ($O(n\log n)$ total).
• Segment tree of sorted vectors (merge sort tree): count $\le x$ in $[l,r)$ in $O({\log }^{2}n)$ (Order Statistics).
• Segment tree on a tree: via Euler tour (subtrees) or HLD (paths).
• Segment tree of segment trees (2D): point update and rectangle query for any monoid in $O({\log }^{2}n)$, memory $O(nm)$ dense or $O(q{\log }^2)$ dynamic. No lazy propagation across the outer dimension.
• Segment tree over time / over queries: offline deletion (Offline Techniques), and segment tree graph construction for range edges (segment tree graph).
• Dynamic / sparse (nodes created on demand) and persistent (old versions kept): when the coordinate range is too large to allocate upfront, or past versions must be queryable — see Dynamic and Persistent Segment Trees.
• Beats (chmin/chmax with range sum): when a node’s aggregate can’t be updated in $O(1)$ from a chmin/chmax tag alone — see Segment Tree Beats.

Fenwick or segment tree?

Use a Fenwick tree for invertible operations with point updates (smaller and faster). Use a segment tree for non-invertible operations (min, max, gcd), complex nodes, descents, or lazy range updates.

	Fenwick	Segment tree
code	~15 lines	more boilerplate
memory	$O(n)$	$O(4n)$ recursive, $O(2\cdot 2^{\lceil \log n\rceil })$ bottom-up
operation	mainly invertible (sum, xor)	any associative op
range update + range query	needs two Fenwicks (trick)	native, via lazy propagation
min/max	prefix only, monotone updates	fully native
chmin/k-th/persistence	not designed for it	dedicated variants exist (Beats, persistent, merge sort tree)
constant factor	smaller	larger, far more general

Pitfalls

• The identity e() must truly be neutral: for min use $+\infty$, for gcd use 0, for matrices the identity matrix.
• Recursive trees need about $4n$ nodes. Bottom-up trees need $2\cdot$ the next power of two (or $2n$ with the non-power-of-two layout, which breaks order for non-commutative ops and the descents).
• Out-of-range queries with $l=r$ should return e().