Segment tree
Overview
A binary tree used for storing intervals or segments, allowing querying and updating of array intervals in logarithmic time.
It bridges the gap between fast updates and fast queries, providing O(log n) for both.
Where used: Computational geometry (stabbing queries), Dynamic Range Minimum Query (RMQ), Game development (collision detection)
Why it exists
Problem: We need to repeatedly update elements in an array AND query range sums/mins/maxes interleaved. Prefix sums give O(1) queries but O(n) updates. Arrays give O(1) updates but O(n) queries.
Naive approach: Use a standard array (O(n) queries) or prefix sum array (O(n) updates).
Better idea: Build a binary tree over the array where each node represents a range (segment). Updating a leaf takes O(log n) as we bubble up. Querying a range takes O(log n) by combining covering segments.
Why learn this
- It is the ultimate hammer for any 'range query with updates' problem.
- It teaches how to map tree structures into flat arrays.
Mental model
It's like a corporate management hierarchy. The CEO knows the total revenue. VPs know the revenue of their halves. Managers know quarters. If one employee updates their sales, the change bubbles up to the CEO in O(log n) time.
A Segment Tree stores intervals. The root stores the sum (or min/max) of the whole array `[0, N-1]`. Its left child stores `[0, mid]`, and right child `[mid+1, N-1]`. Leaves are single elements. Range queries recursively combine segments that perfectly cover the target range.
Repeated decision: Does this node's segment perfectly overlap with the query? If yes, return its value. If partial, split the query to the children. If none, return a null/zero value.
Deep dive
A Segment Tree is a full binary tree. Even though it's a tree, we rarely use Node classes with `left` and `right` pointers. Instead, like a Binary Heap, we map it into a flat array of size `4N`.
The root is at index `1` (representing the whole array). For any node at index `i`, its left child is at `2i` and its right child is at `2i + 1`. The value at a node is the sum (or min, or max) of its children.
**To Update:** Start at the root and recursively find the leaf representing the index you want to update. Change the leaf's value. As the recursion unwinds, update the parent's value based on the new child values. This touches one path from root to leaf, taking `O(log n)`.
**To Query:** Start at the root. You are given a target range `[L, R]`.
- If the node's range is entirely inside `[L, R]`, just return the node's value!
- If the node's range is entirely outside `[L, R]`, return a neutral value (0 for sum, infinity for min).
- If it partially overlaps, ask both children and combine their answers.
Because we grab pre-computed chunks whenever they fit perfectly, we only explore at most `O(log n)` nodes per query.
Key points
- Complexity: Build takes O(N). Point Updates and Range Queries take O(log N). Space takes O(N) (specifically, an array of size 4N is safe).
- Lazy Propagation: If you need to update a RANGE of elements at once, standard Segment Trees take O(N). You must use an advanced technique called 'Lazy Propagation' to defer updates, bringing Range Updates down to O(log N).
Pattern: Segment Tree
Recognition cues:
- Update an element
- Query a range
- Data changes over time
Failure signals
- The data is highly multi-dimensional (requires 2D/3D trees, which are complex).
Engineering examples
Database indexing
Finding all events that overlap with a specific time window.
Segment trees (or Interval Trees) can quickly find all intervals overlapping a query point or range.
When not to use
- Static Arrays (No updates): If the array never changes, just use Prefix Sums (for sum) or a Sparse Table (for min/max) which give O(1) queries and are much easier to code.
Common mistakes
- Array size is too small: A segment tree requires an array of size `4 * N` to guarantee enough space for all leaves and internal nodes. Using `2 * N` will cause out-of-bounds errors on non-power-of-two arrays.
- Wrong default return for outside ranges: If a query goes completely outside the target range, it must return a value that doesn't affect the result. For sum, return `0`. For min, return `infinity`. Returning `0` for a min-query will incorrectly make 0 the minimum.
Recall questions
- What is the time complexity of a Range Query in a Segment Tree?
- What size array should you allocate for a Segment Tree covering N elements?
- If a query perfectly covers a segment tree node's range, what does the recursive function do?
Understanding checks
You have a Segment Tree built for Range Minimum Query. What value should a node return if its segment is completely outside the requested query range?
Positive infinity.
Infinity acts as the identity element for the `min` operation. When combined via `min(infinity, valid_child_result)`, it safely ignores the outside path.
If you update the element at index 3 in a Segment Tree of size 8, how many nodes in the tree will be modified?
4 nodes (the leaf at index 3, its parent, its grandparent, and the root).
A point update modifies exactly one path from the leaf to the root. Since the depth is log2(8) = 3, the path length is 4.
Questions & answers
Range Sum Query - Mutable
This is the exact definition of a Segment Tree (or Fenwick Tree).
Approach: Implement `build()`, `update()`, and `query()` using the recursive divide-and-conquer template.
Practice tasks
Range Sum Query - Mutable
Implement a class `NumArray` that supports updating an element and calculating the sum of elements in `[left, right]`.
Continue learning
Previous: Recursive tree thinking