Segment trees: point update, range query

Fenwick is brilliant but narrow: it loves invertible aggregates. For range min, range max, range gcd, or any aggregate you cannot subtract back out, the segment tree is the general answer. It is a binary tree laid over the array: each node stores the aggregate of a contiguous segment, leaves are single elements, and the root covers the whole array.

A node owning [lo, hi] splits at mid = (lo+hi)/2 into a left child [lo, mid] and a right child [mid+1, hi]. Its stored value is the op of its two children. There are about 2n nodes total and the tree is ⌈log₂ n⌉ deep.

int query(int node, int lo, int hi, int l, int r) {
    if (r < lo || hi < l) return NEUTRAL;     // disjoint: contributes nothing
    if (l <= lo && hi <= r) return tree[node]; // fully inside: take it whole
    int mid = (lo + hi) / 2;
    return op(query(2*node,   lo,    mid, l, r),
              query(2*node+1, mid+1, hi,  l, r));
}

A query of [l, r] recurses from the root. Three cases at each node: the node's segment is disjoint from [l, r] (return the neutral element — +∞ for min, 0 for sum), fully inside (return the stored aggregate, no recursion), or partial (recurse into both children). The query touches O(log n) nodes because [l, r] is tiled by at most two nodes per level.

A point update — set a[i] = x — walks the single root-to-leaf path to i, rewrites the leaf, and on the way back up recomputes each parent from its children. One path, O(log n) nodes.

So why ever use Fenwick? Constant factor and code length: Fenwick is a third the code and noticeably faster for plain sums. The segment tree earns its extra weight when the aggregate is non-invertible, or when you need its real superpower — updating a whole range at once, which the next lesson unlocks.