Log inSign up
hardGeeksforGeeksNot Started

Merge Sort Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on GeeksforGeeks
Lesson

Problem Statement

A Merge Sort Tree is a Segment Tree data structure where each node stores a sorted vector of elements belonging to its subsegment.

Given an array of integers nums of size n and an array of queries where each query is given as [L, R, k] (0-indexed range [L, R]), count the number of elements in the subarray nums[L...R] that are strictly greater than k.

Return an array containing the answer for each query.

Merge Sort Trees answer such queries in O(log^2 n) time by dividing the query interval into O(log n) canonical tree nodes and performing binary search on each.

Example 1 · Example 1:

Input: nums = [7, 3, 9, 1, 5, 2], queries = [[0, 4, 4], [1, 5, 2], [2, 3, 5]]
Output: [3, 3, 1]
Explanation: For query [0, 4, 4]: subarray nums[0..4] is [7, 3, 9, 1, 5]. Elements > 4 are 7, 9, 5 (3 elements). For query [1, 5, 2]: subarray nums[1..5] is [3, 9, 1, 5, 2]. Elements > 2 are 3, 9, 5 (3 elements). For query [2, 3, 5]: subarray nums[2..3] is [9, 1]. Elements > 5 is 9 (1 element).

Example 2 · Example 2:

Input: nums = [2, 4, 6, 8, 10], queries = [[0, 4, 6], [1, 3, 3]]
Output: [2, 3]
Explanation: In [2, 4, 6, 8, 10], elements > 6 are 8 and 10 (2 elements). In [4, 6, 8], elements > 3 are 4, 6, 8 (3 elements).

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= queries.length <= 105
  • 0 <= L <= R < nums.length
  • -109 <= nums[i], k <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for Merge Sort Tree.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Merge Sort Tree
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: When queries are few (Q <= 100).
  • BETTER: When square root decomposition is preferred for simplicity or if block updates are needed.
  • OPTIMAL: The definitive standard for static 2D range counting queries (range + value filter).

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Direct Range Iteration

Intuition

For each query, initialize a counter to 0 and iterate through each index i from L to R. If nums[i] > k, increment the counter. Processing each query takes O(R - L + 1) = O(n) time. With Q queries, the overall time is O(Q \cdot n), which is too slow for large inputs.

When to apply: When queries are few (Q <= 100).

Algorithm

  1. Step 1: Iterate through each query [L, R, k].
  2. Step 2: Initialize count = 0.
  3. Step 3: Loop i from L to R; if nums[i] > k, increment count.
  4. Step 4: Record count in results array.
  5. Step 5: Return results.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4std::vector<int> solveBruteForce(const std::vector<int>& nums, const std::vector<std::vector<int>>& queries) {
5 std::vector<int> res;
6 res.reserve(queries.size());
7 for (const auto& q : queries) {
8 int l = q[0], r = q[1], k = q[2];
9 int count = 0;
10 for (int i = l; i <= r; ++i) {
11 if (nums[i] > k) count++;
12 }
13 res.push_back(count);
14 }
15 return res;
16}
17
18int main() {
19 std::vector<int> nums = {7, 3, 9, 1, 5, 2};
20 std::vector<std::vector<int>> queries = {{0, 4, 4}, {1, 5, 2}, {2, 3, 5}};
21 auto ans = solveBruteForce(nums, queries);
22 for (int x : ans) std::cout << x << " ";
23 std::cout << std::endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(Q * n) time
  • Space complexity: O(1) auxiliary space (excluding results)

2. Square Root Decomposition (Block Sorting)

Intuition

Divide the array into blocks of size B = \lceil \sqrt{n} \rceil. For each block, keep a copy of the elements sorted in ascending order. When answering query [L, R, k]: - For partial blocks at the boundaries, scan the elements directly and count those > k. - For completely covered blocks, use binary search (upper_bound) on the sorted block in O(log B) time to find elements > k as \text{blockSize} - \text{upper\_bound}(k). Total query time is O(\sqrt{n} log \sqrt{n}), considerably faster than O(n) linear scans.

When to apply: When square root decomposition is preferred for simplicity or if block updates are needed.

Algorithm

  1. Step 1: Set block size B = ceil(sqrt(n)) and partition nums into blocks.
  2. Step 2: Pre-sort elements in each block.
  3. Step 3: For query [L, R, k], scan partial block elements at left and right boundaries directly.
  4. Step 4: For whole blocks in between, count elements > k using upper_bound.
  5. Step 5: Return summed counts.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cmath>
4#include <algorithm>
5
6std::vector<int> solveSqrtDecomp(const std::vector<int>& nums, const std::vector<std::vector<int>>& queries) {
7 int n = nums.size();
8 int b = std::max(1, (int)std::sqrt(n));
9 int numBlocks = (n + b - 1) / b;
10 std::vector<std::vector<int>> blocks(numBlocks);
11
12 for (int i = 0; i < n; ++i) {
13 blocks[i / b].push_back(nums[i]);
14 }
15 for (auto& block : blocks) {
16 std::sort(block.begin(), block.end());
17 }
18
19 std::vector<int> res;
20 res.reserve(queries.size());
21
22 for (const auto& q : queries) {
23 int l = q[0], r = q[1], k = q[2];
24 int count = 0;
25 int startBlock = l / b, endBlock = r / b;
26
27 if (startBlock == endBlock) {
28 for (int i = l; i <= r; ++i) if (nums[i] > k) count++;
29 } else {
30 for (int i = l; i < (startBlock + 1) * b; ++i) if (nums[i] > k) count++;
31 for (int block = startBlock + 1; block < endBlock; ++block) {
32 auto it = std::upper_bound(blocks[block].begin(), blocks[block].end(), k);
33 count += (blocks[block].end() - it);
34 }
35 for (int i = endBlock * b; i <= r; ++i) if (nums[i] > k) count++;
36 }
37 res.push_back(count);
38 }
39 return res;
40}
41
42int main() {
43 std::vector<int> nums = {7, 3, 9, 1, 5, 2};
44 std::vector<std::vector<int>>& queries = *new std::vector<std::vector<int>>{{0, 4, 4}, {1, 5, 2}, {2, 3, 5}};
45 auto ans = solveSqrtDecomp(nums, queries);
46 for (int x : ans) std::cout << x << " ";
47 std::cout << std::endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(n log n + Q * sqrt(n) log(sqrt(n))) time
  • Space complexity: O(n) auxiliary space for sorted blocks

3. Merge Sort Tree (O(log^2 n) per Query)

Intuition

A Merge Sort Tree is built like Merge Sort: 1. Tree Construction: - Leaf node i holds the single element [nums[i]]. - Internal node [start, end] merges sorted vectors of its left and right children using two pointers in O(end - start + 1). - Each level contains exactly N elements across all nodes. With \lceil \log_2 N \rceil levels, total construction time is O(n log n), and space is O(n log n). 2. Querying Range [L, R] with threshold k: - The range [L, R] decomposes into at most 2 \lceil \log_2 N \rceil disjoint canonical segment tree nodes. - In each canonical node, find the number of elements strictly greater than k using std::upper_bound (binary search in O(log(\text{nodeSize})) <= O(log n)). - Elements greater than k: \text{node.vector.size()} - \text{upper\_bound}(k). - Sum these counts across all canonical nodes. 3. Total time per query is O(log2 n), which answers 100,000 queries easily in under 150ms.

When to apply: The definitive standard for static 2D range counting queries (range + value filter).

Algorithm

  1. Step 1: Allocate tree vector of size 4 * n.
  2. Step 2: Build tree: leaf stores [nums[idx]], internal node merges children sorted lists.
  3. Step 3: Define query(node, start, end, l, r, k): if disjoint return 0; if fully contained, binary search upper_bound(k) and return vector.size() - upper_bound.
  4. Step 4: Else recurse on children and return sum.
  5. Step 5: Run query for each [L, R, k] and return answers.

Interactive trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Build Merge Sort Tree for nums = [7, 3, 9, 1, 5, 2]
Visual state
Values and pointers at this exact step
pointers
S
1
2
3
5
7
9
0
1
2
3
4
5
Check / comparison
Tree height = ceil(log2(6)) = 3
Decision / next transition
Ready to answer queries
Why this step matters

Build Merge Sort Tree for nums = [7, 3, 9, 1, 5, 2]. Root node covers [0, 5] with sorted elements [1, 2, 3, 5, 7, 9].

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5struct MergeSortTree {
6 int n;
7 std::vector<std::vector<int>> tree;
8
9 MergeSortTree(const std::vector<int>& arr) : n(arr.size()), tree(4 * arr.size()) {
10 build(1, 0, n - 1, arr);
11 }
12
13 void build(int node, int start, int end, const std::vector<int>& arr) {
14 if (start == end) {
15 tree[node] = {arr[start]};
16 return;
17 }
18 int mid = (start + end) / 2;
19 build(2 * node, start, mid, arr);
20 build(2 * node + 1, mid + 1, end, arr);
21 std::merge(tree[2 * node].begin(), tree[2 * node].end(),
22 tree[2 * node + 1].begin(), tree[2 * node + 1].end(),
23 std::back_inserter(tree[node]));
24 }
25
26 int query(int node, int start, int end, int l, int r, int k) {
27 if (r < start || end < l) return 0;
28 if (l <= start && end <= r) {
29 auto it = std::upper_bound(tree[node].begin(), tree[node].end(), k);
30 return tree[node].end() - it;
31 }
32 int mid = (start + end) / 2;
33 return query(2 * node, start, mid, l, r, k) + query(2 * node + 1, mid + 1, end, l, r, k);
34 }
35};
36
37std::vector<int> countGreaterThan(const std::vector<int>& nums, const std::vector<std::vector<int>>& queries) {
38 MergeSortTree mst(nums);
39 std::vector<int> ans;
40 ans.reserve(queries.size());
41 for (const auto& q : queries) {
42 ans.push_back(mst.query(1, 0, (int)nums.size() - 1, q[0], q[1], q[2]));
43 }
44 return ans;
45}
46
47int main() {
48 std::vector<int> nums = {7, 3, 9, 1, 5, 2};
49 std::vector<std::vector<int>> queries = {{0, 4, 4}, {1, 5, 2}, {2, 3, 5}};
50 auto ans = countGreaterThan(nums, queries);
51 for (int x : ans) std::cout << x << " ";
52 std::cout << std::endl;
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(n log n) construction; O(Q * log^2 n) query time
  • Space complexity: O(n log n) auxiliary space for the Merge Sort Tree

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Direct Range IterationO(Q * n) timeO(1) auxiliary space (excluding results)For each query [L, R, k], loop through the subarray nums[L..R] and count elements strictly greater than k.O(Q * n) time
2.Square Root Decomposition (Block Sorting)O(n log n + Q * sqrt(n) log(sqrt(n))) timeO(n) auxiliary space for sorted blocksDivide nums into blocks of size B = sqrt(n). Keep a sorted copy of each block. Full blocks use binary search; partial blocks use linear scans.O(n log n + Q * sqrt(n) log(sqrt(n))) time
3.Merge Sort Tree (O(log2 n) per Query)OptimalO(n log n) construction; O(Q * log^2 n) query timeO(n log n) auxiliary space for the Merge Sort TreeConstruct a Segment Tree where each node merges its child sorted vectors. Query by breaking [L, R] into O(log n) nodes and binary searching elements > k.O(n log n) construction; O(Q * log2 n) query time

Common Pitfalls & Crucial Edge Cases

Attempting point updates without understanding complexity

Updating an element in a Merge Sort Tree requires modifying O(log N) vectors, taking O(N) or O(log2 N) with balanced trees. It is primarily an offline/static data structure.

Using linear scan inside segment nodes

Must use std::upper_bound or std::lower_bound to achieve O(log N) per node.

Forgetting to merge child vectors during build

Use std::merge on children vectors to build parent nodes in linear time per level.

Crucial Edge Cases to Validate:

  • All elements in range are greater than k — Binary search returns 0.
  • All elements in range are less than or equal to k — Binary search returns node segment length.
  • Range covers single element (L == R) — Leaf node vector has size 1.
  • Large N = 10^5 — Total vector memory is ~105 * 17 * 4 bytes ≈ 7 MB, well within standard memory limits.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the construction: exactly matches the execution trace of Merge Sort, storing the state of every merge step.
  2. Contrast with Persistent Segment Tree: Merge Sort Tree takes O(log2 N) for K-th smallest queries (via binary search on answer), whereas PST takes O(log N).
  3. Point out that Merge Sort Tree is simpler to implement and requires no complex pointer manipulation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What does each node in a Merge Sort Tree store?

2.How does a Merge Sort Tree answer queries like 'count elements <= k in range [L, R]' in O(log2 N) time?

3.What is the memory complexity of a Merge Sort Tree over N elements?

Back to DSA Sheet