Skip to main content
Segment Tree

Merge Sort Tree

Each segment tree node stores a sorted list of elements in its range. Enables order-statistic queries like 'how many elements in range [L,R] are less than K?' by binary searching at O(log² n) per query.

O(n log²n)
·
O(n log n)

How It Works

A merge sort tree is a segment tree whose every node stores the sorted list of all elements in its range — exactly the intermediate arrays produced during merge sort, retained level by level. Construction merges children's lists upward in O(n log n) time and space, since each element appears in one node per level across O(log n) levels.

Order-statistic range queries then decompose as usual: a query like 'how many elements in [L, R] are less than K' visits the O(log n) canonical nodes covering the range and binary searches each node's sorted list, costing O(log^2 n) per query. That answers count-smaller, kth-smallest (with an extra binary search on the answer), and rank queries on arbitrary subarrays — questions a plain segment tree cannot express because sums and mins destroy the distributional information the sorted lists preserve. The structure is static; point updates would require rebuilding lists along a root-to-leaf path.

Step-by-Step Visualization

Merge sort tree: each node has sorted subarray
3
0
1
1
4
2
1
3
5
4
Root[1,1,3,4,5]
1/3

Code

Java
// Each node stores sorted array of elements in range
// Build: merge left and right children's sorted arrays
// Query count of elements < k in range [l,r]:
// binary search in each visited node's sorted array

Tips & Gotchas

1Each segment tree node stores sorted list of elements in its range
2Enables order-statistic queries on any subarray
3Build by merging children's sorted lists

Practice Problems

  • 1Count of Smaller Numbers After Self
  • 2Count of Range Sum
  • 3Reverse Pairs

About the Segment Tree Pattern

A binary tree where each node represents a range of the array. Leaves are individual elements. Internal nodes store the aggregate (sum, min, max) of their children's ranges. Supports both queries and updates in O(log n).

Key insight

If you only need prefix queries with point updates, use a BIT (simpler). If you need arbitrary range queries + range updates, use a segment tree with lazy propagation. Sparse table is O(1) query but static.

Common Range Structures Interview Problems

  • Range Sum Query - Mutable
  • Count of Smaller Numbers After Self
  • Range Minimum Query
  • Longest Increasing Subsequence (BIT approach)

Frequently Asked Questions

How does a merge sort tree differ from a normal segment tree?

A normal segment tree collapses each range to a single scalar aggregate, which cannot answer distribution questions like 'how many values are below K'. The merge sort tree keeps the entire sorted multiset per node, trading O(n log n) space for the ability to binary search within any canonical range piece.

Why is the total space O(n log n) and not O(n^2)?

Each array element belongs to exactly one node's range at each of the O(log n) tree levels, so the summed length of all stored lists is n per level times log n levels. The per-node lists overlap across levels, but within a level the ranges partition the array.

Can a merge sort tree handle updates?

Not efficiently — changing one element invalidates the sorted lists of all O(log n) ancestors, and inserting into a sorted array is O(n) per node. Dynamic order-statistic ranges call for a different tool: a BIT of BITs, a wavelet tree, or a segment tree with balanced BSTs at nodes.