Segment Tree

What is a Segment Tree?

A segment tree stores summaries for nested ranges of an array. The root describes the whole array, and each child describes half of its parent's range.

You need binary trees, recursion or iterative tree indexes, and an associative combine operation. The short version is: precompute range summaries in a tree so one update or query touches only logarithmically many summaries.

The Core Idea: Reuse Whole Segments

In LC 307: Range Sum Query, the array is [1,3,5,7,9,11]. A query for indexes 1 through 4 does not need to visit each value separately.

Which stored nodes can answer it? We take every tree segment lying completely inside the query and combine their sums. Segments outside the range contribute nothing.

It is like totaling sales by using completed weekly reports instead of reopening every receipt. Only the partial weeks at the edges need to be broken into smaller groups.

How a Range Query Chooses Nodes

The Rule You Keep True

Every node stores the correct combined answer for exactly the segment assigned to that node. After an update, that statement must be restored from the changed leaf up to the root.

The operation changes the stored value and neutral element:

• Range sum combines with addition and uses zero for no overlap.
• Range minimum combines with min and uses infinity for no overlap.
• Point update replaces one leaf and recomputes ancestors.
• Range module needs lazy or interval-aware updates when entire ranges change.

LC 307: Point Update is the one that usually trips us up. Changing the array value is only the first step. Every parent whose segment contains that index must be recomputed or later queries will read stale data.

Picking the Right Shape

From Rule to Code

1. Define the segment represented by each node and the neutral value for no overlap.
2. Build leaves from the array and combine children to fill parents.
3. For a query, return on no overlap or full overlap and recurse on partial overlap.
4. For an update, change the leaf and recompute every ancestor.
5. Return the root or combined query result after all affected nodes are correct.

Build time is O(n), while each point update and range query touches O(log n) tree levels.