DSA Notes

Range Queries

Segment Tree

Answer range questions and change single elements, both in O(log n).

The idea

A segment tree is a binary tree over the array. The root covers the whole array, each node splits its range in half, and the leaves are single elements. Every node stores the answer for its range: a sum, a minimum, a maximum.

A query for [u, v] is assembled from O(log n) nodes that lie fully inside the range. Changing one element only affects the O(log n) nodes on the path from its leaf to the root.

It works for any operation where two neighbouring ranges can be combined into one. If the array never changes, prefix sums or a sparse table are simpler.

Sample problem

307. Range Sum Query - Mutable ↗ Medium

Design a structure over an array that supports two operations, mixed in any order: update one element, and return the sum of the elements between two indices.

nums = [1,3,5,7,2,4,6,8]
sumRange(2, 6) → 24
update(3, 10)
sumRange(2, 6) → 27

Why the solution works

A plain array makes updates O(1) but sums O(n). Prefix sums make sums O(1) but every update O(n). With many of both, each is too slow.

A segment tree balances the two. Each node stores the sum of a segment, and its children split that segment in half. A range is covered by O(log n) whole nodes, so a query adds up those; an element lies in one node per level, so an update fixes O(log n) nodes.

The two early returns in query are the whole trick: stop when a node is outside the range, and stop when it is fully inside.

Complexity: O(n) to build, O(log n) per update and per query, O(n) memory.

Watch out

  • Allocate 4 · n nodes.
  • Return the neutral value when there is no overlap: INT_MAX for min, 0 for sum.
  • Recompute a node from its children after every update below it.
Watch it run

Practise on LeetCode