为何用线段树解决区间最小值查询的时间复杂度为O(log n)？

Great question—this is a common sticking point when first working with segment trees! Let’s break down why even when you have to split your search across nodes, the time complexity stays at O(log n).

First, a Quick Recap of Segment Tree Structure #

A segment tree is a complete binary tree where:

• Each leaf node represents a single element from your input array.
• Internal nodes store the merged result (in this case, the minimum value) of their child nodes’ intervals.
• The height of the tree is h = ⌈log₂(n)⌉, where n is the size of the input array. This means there are only log n levels in total.

How the Query Process Works (and Why It’s Efficient) #

When querying for the minimum in range [L, R], we traverse the tree from the root, following three rules for each node:

• If the node’s interval is completely inside [L, R]: We take the node’s stored minimum and stop traversing this branch—no need to go deeper, we already have the min for this subrange.
• If the node’s interval is completely outside [L, R]: We ignore this branch entirely, it contributes nothing to our query.
• If the node’s interval partially overlaps with [L, R]: We recursively query both the left and right child nodes, then take the minimum of those two results.

The Key Insight: Limited Nodes Per Level #

The critical point here is that on every level of the tree, we will only ever process at most 2 nodes that require further recursion.

Here’s why:
Imagine your query range cuts across a node’s interval. When you split into left and right children, one of those children might still partially overlap with [L, R], but the other will either be fully included or fully excluded. As you go down each level, you never end up with more than 2 "active" nodes that need to be split further.

Since the tree has only log n levels, the total number of nodes we process is 2 * log n—which simplifies to O(log n) time.

Example to Make It Concrete #

Let’s say we have an array [1, 3, 5, 7, 9, 11] (n=6, log₂(6) ≈ 2.58, so tree height is 3). We want to query the minimum in range [1, 4]:

1. Root node (interval [0,5]): Partially overlaps with [1,4], so we query left child [0,2] and right child [3,5].
2. Level 2:
   • Left child [0,2]: Partially overlaps with [1,4], so query its left child [0,1] and right child [2,2].
   • Right child [3,5]: Partially overlaps with [1,4], so query its left child [3,4] and right child [5,5].
3. Level 3:
   • [2,2] is fully inside [1,4] → return its value (5) and stop.
   • [3,4] is fully inside [1,4] → return its value (7) and stop.
   • [0,1] partially overlaps with [1,4], so query its left child [0,0] (fully outside, ignored) and right child [1,1] (fully inside, returns 3).
4. We combine the results: min(3,5,7) = 3.

Count the nodes we processed: 1 (root) + 2 (level 2) + 3 (level 3) = 6 nodes. That’s 2 * 3 (tree height) = 6, which aligns with our O(log n) calculation.

Final Takeaway #

Even when you have to split your query across nodes, the number of nodes you need to process scales linearly with the tree’s height—which is log n. You never end up traversing a large portion of the tree, because most nodes are either fully included (return immediately) or fully excluded (ignored).

内容的提问来源于stack exchange，提问作者Ori Benami