"Tell me this range sum, fast"

Suppose you have the array [5, 8, 6, 3, 2, 7, 2, 6]. Someone asks: "What's the sum from index 2 to 5?" (6+3+2+7 = 18)

Once is easy — just add them. But what if such questions come hundreds of thousands of times, and values change in between? Summing the range from scratch each time costs O(n) per query — you'll time out fast.

Example: query(2, 5) → 18. Then change arr[4] from 2 to 10, and query(2, 5) → 6+3+10+7 = 26.

Won't prefix sums do? (Only half right)

"Let's precompute everything" leads to prefix sums. Store the sum of 0..i in prefix[i], and a range sum becomes prefix[r] - prefix[l-1] in O(1).

For queries alone, it's perfect. The problem is updates. Change just arr[4], and every prefix[4], prefix[5], ... after it is now wrong. One update costs O(n) all over again.

•Prefix sum: query O(1) / update O(n) ← deadly when values change often
•What we want: both query and update to be fast

Why group into a tree? — "Pre-combine the ranges"

Here's the shift. Split the array into segments, and write each segment's sum into a node ahead of time.

•Leaf: one element ([4-4])
•Internal node: the merge of two child ranges ([4-5], [4-7] …)
•Root: the whole thing ([0-7])

Something neat happens. To get the sum of [2-5], you pick just two nodes: [2-3] (sum 9) and [4-5] (sum 9), add them, and get 18. Instead of adding 4 elements one by one, you combined two pre-summed chunks.

The key rule is parent sum = sum of two children. Thanks to it, any range can be covered by O(log n) node pieces.

Updates fix just one strand

What about when a value changes? To set arr[4] to 10:

1. Set leaf [4-4] to 10

2. Re-sum its parent [4-5] (9 → 17)

3. Then its parent [4-7] (17 → 25)

4. The root [0-7] (39 → 47)

You only re-add the nodes on one path (strand) from leaf to root. Since the tree height is log n, updates are O(log n) too. A different league from prefix sums' O(n) updates.

Balance is the point. A segment tree makes queries O(log n) *and* updates O(log n) — both fast. It shines exactly when values keep changing.

See it with your own eyes

We built the entire process as a step-by-step visualization: the tree filling up from leaves to root, a query descending the ranges and picking only the covered nodes to combine, and an update riding one strand from leaf to root, fixing sums as it goes. You'll see the range and sum each node owns, all at a glance.

👉 Segment Tree — watch the step-by-step visualization