Segment Tree

A tree of array slices that answers any range query, and applies any point update, in O(log n).

A segment tree answers questions about *ranges* of an array — like "what is the sum of positions 3 through 9?" — without re-adding the numbers every time. Each node stores the answer for one contiguous slice of the array: the root covers the whole thing, and each node splits its slice between two children, all the way down to single elements.

The problem it solves

A plain array can do a point update in O(1) but a range sum in O(n). A prefix-sum array flips that — O(1) sums but O(n) to update. A segment tree refuses the trade-off: it makes both range query and point update O(log n).

How a range query stays cheap

The trick is how the query descends. At each node it asks how the node's slice relates to the query range:

1No overlap — the node's slice is entirely outside the query -> return the identity (0 for sums) and stop.
2Total cover — the node's slice sits entirely inside the query -> return that node's stored aggregate whole, no recursion.
3Straddle — the slice only partly overlaps -> recurse into *both* children and combine their answers.

Because only the straddling nodes split, a query touches at most a couple of nodes per level — about 2 log n in total.

Worked example — sum over [1..3]

array:  index  0  1  2  3
        value  2  5  1  4

             [0..3]=12
            /        \
      [0..1]=7      [2..3]=5
      /    \        /    \
  [0]=2  [1]=5   [2]=1  [3]=4

query sum[1..3]:
  [0..1] straddles -> recurse: [0] no-overlap=0, [1] cover=5
  [2..3] total cover -> 5
  answer = 5 + 5 = 10   (touched ~3 nodes, not 3 elements)

A point update — say array[2] += 6 — walks the single path from the leaf [2] up to the root, re-summing each ancestor on the way. One path, O(log n) nodes touched.

Not just sums

The aggregate a node stores can be *any* associative operation — minimum, maximum, gcd, or sum. Swap the combine step and the same tree answers range-min or range-max queries just as fast. For *range* updates, add lazy propagation to defer pushing changes down until needed.

OperationTimeSpace

Build · ~2n nodes totalO(n)O(n)

Range query · only straddling nodes splitO(log n)O(log n)

Point update · one leaf-to-root pathO(log n)O(1)

Check yourself

Why does a segment tree range query touch only about log n nodes instead of every element in the range?