Merge sort tree for range order queries

Why this matters

A segment tree in this module stores one number in each node, such as a sum or a minimum. That is enough for questions like "what is the total of positions 2 to 6". It is not enough for a question like "how many values in positions 2 to 6 are less than 4". The answer depends on the actual values, not on one combined number.

A merge sort tree handles that kind of question. Each node stores the sorted list of values in its segment. A query then adds up counts from a few nodes, and each count is a quick search in a sorted list.

This lesson builds the structure from scratch. It uses the recursive tree walk from the building lesson, and it does not explain that walk again. Coordinate compression in the previous lesson solves a related problem with a different tool.

Two terms are used throughout. A merge combines two sorted lists into one sorted list by walking through both lists once, always taking the smaller front value. A binary search finds a value in a sorted list by checking the middle element and throwing away half of the list each step.

The question, in plain words

Here is a small array.

index:  0  1  2  3  4  5  6
value:  5  1  4  2  8  3  7

The query asks for three numbers: a left end l, a right end r, and a bound x. The answer is how many values in positions l to r, both included, are strictly less than x.

For l = 1, r = 4 and x = 4, the values are 1, 4, 2 and 8. The values less than 4 are 1 and 2. The answer is 2. The value 4 itself is not counted, because the question asks for values strictly less than 4.

A plain loop would check each position from l to r. That takes time proportional to the length of the range. With a million positions and a million queries, that is too slow. The merge sort tree answers each query in about log squared n steps.

The idea: sorted lists in the nodes

Build the same tree shape as a normal segment tree. The root covers the whole array. Each node covers half of its parent's range, until a leaf covers one position. The difference is what a node stores. A normal segment tree stores one number. A merge sort tree stores the sorted list of all values in its range.

Here is the tree for the small array. Each line shows a node's range and the sorted list stored there.

[0, 6]  1 2 3 4 5 7 8     root: all seven values, sorted
[0, 3]  1 2 4 5           left half
[4, 6]  3 7 8             right half
[0, 1]  1 5               left quarter of the left half
[2, 3]  2 4
[4, 5]  3 8
[6, 6]  7                 a leaf holds one value
...

The lists at the leaves are single values, so they are not repeated here. The full set of lists is printed in the first worked example below.

Each level of the tree holds every value once. The root holds all n values. The two children hold n values between them. The four grandchildren hold n values between them, and so on. Because the tree has about log2 n levels, the total storage is about n times log2 n numbers.

Building the tree by merging

The lists are built from the bottom up. A leaf's list has one value. A parent's list is the merge of its two children's lists. Because both children lists are already sorted, one merge pass gives the parent's sorted list. There is no need to sort again.

Take the node [0, 3]. Its children are [0, 1] with list 1 5 and [2, 3] with list 2 4. Merging them means: compare the front values 1 and 2, take 1; compare 5 and 2, take 2; compare 5 and 4, take 4; take 5 when only one list is left. The result is 1 2 4 5. The C++ function std::merge does this walk for us.

The build function is shown below. It has the same shape as the build in the building lesson, but each node stores a list instead of one number.

void build(const std::vector<int>& a, int node, int lo, int hi) {
    if (lo == hi) {
        lists_[node] = {a[lo]};
        return;
    }
    int mid = (lo + hi) / 2;
    build(a, 2 * node, lo, mid);
    build(a, 2 * node + 1, mid + 1, hi);
    const std::vector<int>& left = lists_[2 * node];
    const std::vector<int>& right = lists_[2 * node + 1];
    lists_[node].resize(left.size() + right.size());
    std::merge(left.begin(), left.end(), right.begin(), right.end(), lists_[node].begin());
}

The resize call makes room for the merged list before std::merge writes into it. Writing into a list that has no room would be a bug, which the mistakes section shows.

Answering a query with binary search

A query walks the tree the same way the segment tree query does. When a node lies completely inside the query range, the node's sorted list answers the question for all of its values at once. The code asks std::lower_bound for the first position in that list that holds a value at least x. That position is the number of values less than x, because every value before it is smaller than x and the list is sorted.

int query(int node, int lo, int hi, int l, int r, int x) const {
    if (r < lo || hi < l) return 0;
    if (l <= lo && hi <= r) {
        const std::vector<int>& list = lists_[node];
        return static_cast<int>(std::lower_bound(list.begin(), list.end(), x) - list.begin());
    }
    int mid = (lo + hi) / 2;
    return query(2 * node, lo, mid, l, r, x) + query(2 * node + 1, mid + 1, hi, l, r, x);
}

A node that lies outside the range returns 0. A node that partly overlaps the range is split into its two children. A node that lies fully inside the range gives its count with one binary search.

The walk for the query l = 1, r = 4, x = 4 shows how it works. The range 1 to 4 is covered by three nodes: the leaf [1, 1], the node [2, 3] and the leaf [4, 4]. Together they hold the positions 1, 2, 3 and 4.

• The leaf [1, 1] holds 1. That value is less than 4, so its count is 1.
• The node [2, 3] holds 2 4. The first value that is at least 4 is at index 1, so its count is 1. The value 2 is the one counted.
• The leaf [4, 4] holds 8. The first value that is at least 4 is at index 0, so its count is 0.

The three counts add up to 2, which matches the direct check.

Worked example 1: the full program

The program below builds the tree from an array and then answers queries from the input. It is a complete file. Its input is the array length, the array, the number of queries, and then one query per line.

#include <algorithm>
#include <iostream>
#include <vector>
 
// A merge sort tree. Every node stores the sorted values of its segment.
class MergeSortTree {
public:
    explicit MergeSortTree(const std::vector<int>& a)
        : n_(static_cast<int>(a.size())), lists_(4 * static_cast<std::size_t>(n_)) {
        if (n_ > 0) build(a, 1, 0, n_ - 1);
    }
 
    // How many values in a[l..r] (both ends included) are strictly less than x.
    int countLess(int l, int r, int x) const { return query(1, 0, n_ - 1, l, r, x); }
 
private:
    int n_;
    std::vector<std::vector<int>> lists_;
 
    void build(const std::vector<int>& a, int node, int lo, int hi) {
        if (lo == hi) {
            lists_[node] = {a[lo]};
            return;
        }
        int mid = (lo + hi) / 2;
        build(a, 2 * node, lo, mid);
        build(a, 2 * node + 1, mid + 1, hi);
        const std::vector<int>& left = lists_[2 * node];
        const std::vector<int>& right = lists_[2 * node + 1];
        lists_[node].resize(left.size() + right.size());
        std::merge(left.begin(), left.end(), right.begin(), right.end(), lists_[node].begin());
    }
 
    int query(int node, int lo, int hi, int l, int r, int x) const {
        if (r < lo || hi < l) return 0;
        if (l <= lo && hi <= r) {
            const std::vector<int>& list = lists_[node];
            // lower_bound returns the first position holding a value >= x,
            // so that position equals the number of values < x.
            return static_cast<int>(std::lower_bound(list.begin(), list.end(), x) - list.begin());
        }
        int mid = (lo + hi) / 2;
        return query(2 * node, lo, mid, l, r, x) + query(2 * node + 1, mid + 1, hi, l, r, x);
    }
};
 
int main() {
    int n = 0;
    std::cin >> n;
    std::vector<int> a(n);
    for (int& value : a) std::cin >> value;
 
    MergeSortTree tree(a);
 
    int q = 0;
    std::cin >> q;
    for (int i = 0; i < q; ++i) {
        int l = 0, r = 0, x = 0;
        std::cin >> l >> r >> x;
        std::cout << tree.countLess(l, r, x) << '\n';
    }
}

Compile and run it on this input.

7
5 1 4 2 8 3 7
4
1 4 4
0 6 5
4 4 8
2 5 100

$ g++ -std=c++20 -Wall -o merge_tree merge_tree.cpp
$ ./merge_tree < merge-input1.txt
2
4
0
4

The compiler gives no warnings. Check each answer by reading the array.

• 1 4 4: the values at positions 1 to 4 are 1, 4, 2, 8. Less than 4: 1 and 2. The answer is 2.
• 0 6 5: all seven values are 5, 1, 4, 2, 8, 3, 7. Less than 5: 1, 4, 2 and 3. The answer is 4.
• 4 4 8: the only value is 8. It is not less than 8. The answer is 0.
• 2 5 100: the values are 4, 2, 8, 3. All are less than 100. The answer is 4.

To see the lists the program builds, a test copy of the class can print each node's list. The output for this array is below.

node  1: 1 2 3 4 5 7 8
node  2: 1 2 4 5
node  3: 3 7 8
node  4: 1 5
node  5: 2 4
node  6: 3 8
node  7: 7
node  8: 5
node  9: 1
node 10: 4
node 11: 2
node 12: 8
node 13: 3

The root holds the sorted list of all seven values. Node 2 holds the sorted list of positions 0 to 3, which are 5, 1, 4 and 2. Node 3 holds positions 4 to 6, which are 8, 3 and 7.

Worked example 2: a range, not just a bound

The query form in the first example counts values below a bound. Many questions ask for values inside a range, such as "how many values are from 2 to 4". That can be built from two counts, because the values from 2 to 4 are the values below 5 minus the values below 2.

For integer values, the formula is:

count of values in [lo, hi] = countLess(l, r, hi + 1) - countLess(l, r, lo)

Take the array from the first example, the full range 0 to 6, and the values from 2 to 4. The formula uses hi + 1 = 5 and lo = 2. The program gives these two counts.

$ printf '7\n5 1 4 2 8 3 7\n2\n0 6 5\n0 6 2\n' | ./merge_tree
4
1

The count of values below 5 is 4. The count of values below 2 is 1. The difference is 4 - 1 = 3. The values in [2, 4] are 4, 2 and 3, which is 3 values.

The formula needs hi + 1 to be an integer bound. That works for integer data. If the upper bound is the largest possible int, hi + 1 overflows, so that case needs its own check.

Worked example 3: duplicates and a larger case

The third example has repeated values and a longer array. Repeats are common in real data, such as several scores of 4 in a list of grades. The strict "less than" rule matters here. A value equal to x is not counted.

10
4 4 4 1 1 9 2 2 7 4
3
0 9 4
2 5 4
3 3 2

$ ./merge_tree < merge-input2.txt
4
2
1

Check each answer.

• 0 9 4: values below 4 are 1, 1, 2 and 2. That is 4 values. The three 4s are not counted.
• 2 5 4: positions 2 to 5 hold 4, 1, 1 and 9. Values below 4 are the two 1s. The answer is 2.
• 3 3 2: only position 3 is in range, and it holds 1. The value 1 is less than 2. The answer is 1.

Repeated values need no special handling. Each copy sits in its node's sorted list, and std::lower_bound finds the first position with a value at least x, which skips every copy of x.

Cost and memory

Let n be the array length. A query visits about 2 log2 n nodes. At each visited node, one binary search takes about log2 n steps. The total query time is O(log^2 n). For n = 1,000,000, log2 n is about 20. That is a few hundred steps for each query, not a million.

Building the tree does one merge per node. Each level of the tree costs about n steps, and there are about log2 n levels. The build time is O(n log n).

Memory is the cost to watch. Each level stores n values. For n = 1,000,000 there are about 21 levels, so the values take about 21 million 4-byte integers, which is about 84 MB. The outer lists_ vector has 4n entries, and each entry is a std::vector object of 24 bytes. That is about 96 MB for the outer vector alone, before counting the memory each list allocates for its values. The total is about 180 MB for one million values, before the allocation overhead of each list.

Limits of the structure

The merge sort tree is built once and then queried. It does not support changing one value cheaply. A change to one position affects the sorted list of every node that covers it, which is about log n nodes. Each of those lists may need many values moved, so one change can cost O(n) time. For data that changes often, a different structure is needed. The dynamic segment tree lesson later in this module covers a different trade-off.

Common mistakes

Forgetting the include

The function std::merge is in the <algorithm> header. A file that uses it without that include fails to compile. The real compiler message for the file without the line is shown below.

bug_noalg.cpp: In member function ‘void MergeSortTree::build(const std::vector<int>&, int, int, int)’:
bug_noalg.cpp:30:14: error: ‘merge’ is not a member of ‘std’
   30 |         std::merge(left.begin(), left.end(), right.begin(), right.end(), lists_[node].begin());
      |              ^~~~~

The fix is to add #include <algorithm> at the top of the file. The error names the function and the line, so the fix is usually easy to find.

Using upper_bound for a strict count

A common mistake is to use std::upper_bound instead of std::lower_bound in the query. The upper_bound function returns the first position with a value greater than x, so values equal to x are counted too. The program compiles and runs, but the answers are wrong.

$ ./bug_le < merge-input1.txt
3
5
1
4

The correct output for this input is 2, 4, 0, 4. The first answer is 3 instead of 2, because the value 4 at position 2 is counted when x is 4. Use lower_bound for a strict "less than" count, and check the edge case where a stored value equals the bound.

Sizing the tree too small

The tree uses node numbers up to about 4n. A tree with only 2n slots works for some lengths but fails for others. For an array of six values, the recursive layout reaches node 13, and a vector of size 12 does not have that slot. A debug build with -D_GLIBCXX_ASSERTIONS reports the problem.

$ g++ -std=c++20 -Wall -D_GLIBCXX_ASSERTIONS -g -o bug_2n bug_2n.cpp
$ ./bug_2n < merge-input-n6.txt
/usr/include/c++/15/bits/stl_vector.h:1263: constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; reference = std::vector<int>&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.
exit=134

The message says the program asked for an element that does not exist, and the exit code 134 means the program stopped with an abort. Use 4 * n for the size, as this lesson does.

Comparing an int with a size

The size() function of a std::vector returns an unsigned type. Comparing it with an int loop counter gives a warning under -Wall.

for (int i = 0; i < v.size(); ++i) std::cout << v[i] << std::endl;

The compiler reports this line.

bug_sign.cpp:5:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]

The warning is safe to fix. Use std::size_t as the counter type, or compare with a value of the same type. The program in this lesson uses int for node positions, and the sizes are converted with static_cast<int> where they are stored.

Practice

1. Easy. The array is 3, 9, 1, 6. Write the sorted list stored at the root, at node [0, 1] and at node [2, 3].

Show the answer

The root holds 1 3 6 9. Node [0, 1] holds the values at positions 0 and 1, which are 3 and 9, so its list is 3 9. Node [2, 3] holds 1 and 6, so its list is 1 6.

2. Easy. For the array 5 1 4 2 8 3 7, what does countLess(0, 6, 3) return?

Show the answer

It returns 2. The values less than 3 are 1 and 2. The program prints 2 for this query.

3. Medium. Using countLess, write the expression that counts the values in positions l to r that lie from lo to hi, both included. Assume the values are integers. Then give the count for the array 5 1 4 2 8 3 7, the range 0 to 6, and the values from 2 to 4.

Show the answer

The expression is countLess(l, r, hi + 1) - countLess(l, r, lo). For the example, countLess(0, 6, 5) is 4 and countLess(0, 6, 2) is 1. The difference is 3. The values 4, 2 and 3 lie in the range from 2 to 4.

4. Medium. A program stores 1,000,000 values in a merge sort tree. Estimate the memory used by the stored values. Count the integers and multiply by the size of an int. Then estimate the memory used by the outer vector with 4n entries.

Show the answer

There are about 21 levels, and each level holds n = 1,000,000 values. That is about 21 million integers. Each int is 4 bytes, so the values take about 84 MB. The outer vector has 4,000,000 entries of 24 bytes each, which is about 96 MB. The two parts together are about 180 MB, and the allocation overhead of each list adds more.

5. Hard. Explain why one query takes about log squared n steps, not just log n. Name the two things that repeat.

Show the answer

A query visits about 2 log n nodes, because the range is split into at most about two nodes per level. At each node that lies fully inside the range, one binary search runs, and that search takes about log n steps because the node's list can hold up to n values. Two factors of log n multiply, which gives log squared n.

Summary

• A merge sort tree stores the sorted list of values in each node of a segment tree.
• Each parent's list is built by merging its two children's lists, so no full sort is needed at each node.
• A query adds up one binary-search count from each node that lies fully inside the range.
• Use std::lower_bound for a strict "less than" count, and check the edge case where a value equals the bound.
• The structure uses about n log n stored values, so memory is the main cost, and it does not support cheap updates.