Operations on Segment Tree

A segment tree encodes range-aggregate answers as an implicit binary tree over array indices, so any range query or point update touches only the O(log n) nodes whose segments lie on the root-to-leaf paths of the range's boundaries, instead of the O(n) elements inside it.

Recognize the pattern

• Repeated range queries (sum/min/max/gcd) on an array that also gets updated between queries — if the array were static, prefix sums would already solve it in O(1) per query.
• Need both query and update faster than O(n) — segment tree gives O(log n) for both, where prefix-sum arrays give O(1) query but O(n) update.
• The aggregate function is associative (so partial results from disjoint sub-segments can be merged): sum, min, max, gcd, xor all qualify; median does not, directly.

Brute force vs optimal

Segment tree trades a small constant-factor space/time overhead for balanced logarithmic cost on both operations — the right choice whenever updates are frequent.

Complexity, derived

Build

Build visits every tree node exactly once, and the number of nodes is at most 2n − 1 (a full binary tree over n leaves). Each visit does O(1) work (one addition to combine two children), so build is O(n) time, O(n) extra space for the tree array (sized 4n to safely bound a non-power-of-two leaf count).

Query / Update

The tree has height ⌈log₂ n⌉ (it halves the segment at every level). A point update walks exactly one root-to-leaf path, touching one node per level → O(log n) time, O(log n) recursion stack space. A range query recurses into a node only if the node's segment partially overlaps the query range; at each level at most 4 nodes have partial overlap (2 on each boundary), so total visited nodes across log n levels is O(log n) → O(log n) time and space.

Worked example

Array [2, 4, 6, 8, 10, 12] (n=6, not a power of two), tree built by the recursive build(node,start,end) below: tree[1]=42, tree[2]=12, tree[3]=30, tree[4]=6, tree[6]=18. Because n=6 doesn't divide evenly, some interior-looking indices are themselves leaves and their would-be children (10 and 11) are never created: node 5 covers segment [2,2] directly (a leaf), and node 7 covers segment [5,5] directly (a leaf). So the leaf values land at tree[8]=2, tree[9]=4, tree[5]=6, tree[12]=8, tree[13]=10, tree[7]=12 — not a contiguous tree[8..13] block. This asymmetry is exactly why the array is sized 4n rather than 2n.

Query sum(1, 4) — indices 1..4 inclusive (values 4,6,8,10 → expect 28)

Sum = 0 + 4 + 6 + 18 + 0 = 28 ✓. Nine calls total for n=6 (bounded by O(log n) with a small constant).

Update index 2: set to 20 (was 6)

1. Path to leaf: node 1 → node 2 → node 5 (segment [2,2]).
2. tree[5] = 20 (was 6) — the update assigns the new value directly; it does not add a delta.
3. Unwind: tree[2] = tree[4] + tree[5] = 6 + 20 = 26 (was 12).
4. tree[1] = tree[2] + tree[3] = 26 + 30 = 56 (was 42).

Only 3 nodes changed — one per level.

Code (Java)

class SegmentTree {
    int[] tree;
    int n;

    SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[4 * n];
        build(arr, 1, 0, n - 1);
    }

    void build(int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        build(arr, 2 * node, start, mid);
        build(arr, 2 * node + 1, mid + 1, end);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    // sum over [l, r]
    int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;              // no overlap
        if (l <= start && end <= r) return tree[node];    // total overlap
        int mid = (start + end) / 2;                      // partial overlap
        return query(2 * node, start, mid, l, r)
             + query(2 * node + 1, mid + 1, end, l, r);
    }

    void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        int mid = (start + end) / 2;
        if (idx <= mid) update(2 * node, start, mid, idx, val);
        else update(2 * node + 1, mid + 1, end, idx, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}

Pitfalls

• Under-sizing the tree array (using 2n instead of 4n) — for non-power-of-two n the recursion can index beyond 2n, causing ArrayIndexOutOfBounds.
• Forgetting the recombine step after a leaf update (tree[node] = tree[2*node] + tree[2*node+1] on unwind) — leaves ancestor aggregates stale.
• Off-by-one in overlap checks (r < start || end < l vs <=) silently drops or double-counts boundary elements.
• Using a non-associative or non-invertible aggregate (e.g. plain average) without adapting the merge logic — sum/count works, a raw average of children doesn't.
• Assuming leaves always land in a contiguous block of the array (e.g. tree[n..2n-1]) — that's only true when n is a power of two. For other n, some interior-looking indices are themselves leaves (as seen above with tree[5] and tree[7]).

When to use / when not

Use a segment tree when the array is mutated between range queries and the aggregate is associative. Prefer a prefix-sum array instead when the array is static (immutable) — O(1) query beats O(log n) with far less code and 1/4 the memory. Prefer a Fenwick / Binary Indexed Tree when the aggregate is invertible (sum, xor) and only point updates + prefix queries are needed — same O(log n) bounds but ~4x less memory and a simpler implementation (no recursion). Reach for a segment tree specifically when you need range queries with non-invertible aggregates (min, max, gcd) or need lazy propagation for range updates.

Takeaways

• Build is O(n); query and update are each O(log n), derived from tree height ⌈log₂ n⌉ and a bounded number of partially-overlapping nodes per level.
• An update touches exactly one root-to-leaf path; a range query touches O(log n) nodes via the total/partial/no-overlap trichotomy.
• Segment tree beats prefix sums when updates are frequent, and beats brute force whenever n is large and queries repeat.
• For non-power-of-two n, leaves don't sit in one contiguous index block — some interior-looking indices are leaves whose sibling children never get created. This is precisely why the array must be sized 4n, not 2n.

Recall: Why does a point update only need to modify nodes on a single root-to-leaf path, and why does that bound the update cost to O(log n)?

Derived from Segment Tree course material: build/query/update algorithms and a traced worked example over [2,4,6,8,10,12] with n=6.