Segment Tree
The Intuition
Think of a tournament bracket with 8 players. In round 1, player 1 faces player 2, player 3 faces player 4, and so on. Four matches produce four winners. In round 2, those four winners play two matches. In round 3, the final two play for the championship. Seven matches total, organized in a binary tree. The root is the final match. The leaves are the 8 individual players.
Now suppose someone asks: "who's the best player between positions 3 and 6?" You don't need to compare all four of them from scratch. The match between players 3-4 already has a result, and the match between players 5-6 already has a result. You just compare those two pre-computed results. Two lookups instead of four. For a range query on 1,000 players, you'd touch roughly 10 pre-computed match results instead of scanning hundreds of players. That is the log(n) magic of a segment tree.
What about updates? Say player 5 gets stronger. You only need to recalculate the 3 matches they participated in: the round-1 match (5 vs 6), the round-2 match (winner of 5-6 vs winner of 7-8), and the round-3 final. Three updates for 8 players. For n players, that is log(n) updates. You walk up one path from the leaf to the root, recalculating each match along the way.
This works for any "combine two answers" operation, not just finding winners. Replace "who wins" with "sum of scores" and each internal node stores the total score of everyone in its bracket. Replace it with "minimum score" and each node stores the lowest score in its subtree. Any associative operation works.
Lazy propagation handles bulk updates. Suppose the tournament organizer says "add 10 bonus points to every player from positions 3 through 7." You don't walk down to each of those five players immediately. You tag the internal nodes that fully cover sub-ranges of [3, 7] with a "+10 pending" note. Only when someone queries a specific match result within that range do you push the pending update down to the children. This keeps range updates at O(log n) instead of O(n).
The flat array representation (size 4n) just numbers the bracket slots. The root (final match) is position 1. For any node at position i, its two child matches sit at 2i and 2i+1. No pointers, no node objects. Just an array with a clean index formula.
Range sum/min/max queries with updates, count of elements in a range, range assignment/addition, interval scheduling with modifications, or any problem needing efficient aggregate queries on mutable arrays.
No updates needed (use prefix sum, much simpler), need only point queries (use array), or updates are append-only (use BIT/Fenwick tree, less code).
Variations:
- Point update + range query: Update a single index, query a range.
- Range update + range query (lazy propagation): Update an entire range, defer child updates until needed.
- Min/Max segment tree: Replace sum with min/max in the merge step.
- Persistent segment tree: Keep history of all versions for time-travel queries.
- 2D segment tree: Nested segment trees for matrix range queries.
- Single element array
- Query spans the full range of the array
- Large input requiring lazy propagation for efficient range updates
Key Points
- •Binary tree where each node stores aggregate info for a range
- •Build in O(n), query and point update in O(log n)
- •Lazy propagation enables O(log n) range updates
- •Tree is stored in a flat array of size 4*n for simplicity
- •Supports sum, min, max, GCD, or any associative operation
Code Template
1 class SegmentTree:
2 """Segment tree with lazy propagation for range sum queries."""
3 def __init__(self, nums):
4 self.n = len(nums)
5 self.tree = [0] * (4 * self.n)
6 self.lazy = [0] * (4 * self.n)
7 self._build(nums, 1, 0, self.n - 1)
8
9 def _build(self, nums, node, start, end):
10 if start == end:
11 self.tree[node] = nums[start]
12 return
13 mid = (start + end) // 2
14 self._build(nums, 2 * node, start, mid)
15 self._build(nums, 2 * node + 1, mid + 1, end)
16 self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
17
18 def _push_down(self, node, start, end):
19 if self.lazy[node] != 0:
20 mid = (start + end) // 2
21 self._apply(2 * node, start, mid, self.lazy[node])
22 self._apply(2 * node + 1, mid + 1, end, self.lazy[node])
23 self.lazy[node] = 0
24
25 def _apply(self, node, start, end, val):
26 self.tree[node] += val * (end - start + 1)
27 self.lazy[node] += val
28
29 def update_range(self, l, r, val):
30 """Add val to all elements in [l, r]."""
31 self._update(1, 0, self.n - 1, l, r, val)
32
33 def _update(self, node, start, end, l, r, val):
34 if r < start or end < l:
35 return
36 if l <= start and end <= r:
37 self._apply(node, start, end, val)
38 return
39 self._push_down(node, start, end)
40 mid = (start + end) // 2
41 self._update(2 * node, start, mid, l, r, val)
42 self._update(2 * node + 1, mid + 1, end, l, r, val)
43 self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
44
45 def query_sum(self, l, r):
46 """Sum of elements in [l, r]."""
47 return self._query(1, 0, self.n - 1, l, r)
48
49 def _query(self, node, start, end, l, r):
50 if r < start or end < l:
51 return 0
52 if l <= start and end <= r:
53 return self.tree[node]
54 self._push_down(node, start, end)
55 mid = (start + end) // 2
56 return (self._query(2 * node, start, mid, l, r)
57 + self._query(2 * node + 1, mid + 1, end, l, r))
58
59 def point_update(self, idx, val):
60 """Set element at idx to val."""
61 self._point_update(1, 0, self.n - 1, idx, val)
62
63 def _point_update(self, node, start, end, idx, val):
64 if start == end:
65 self.tree[node] = val
66 return
67 mid = (start + end) // 2
68 if idx <= mid:
69 self._point_update(2 * node, start, mid, idx, val)
70 else:
71 self._point_update(2 * node + 1, mid + 1, end, idx, val)
72 self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]Common Mistakes
- Array size too small -- use 4*n to be safe
- Forgetting to push down lazy values before querying children
- Off-by-one errors in the build/query range boundaries