Merge Sort Tree

A segment tree where each node stores the sorted list of the elements in its range. Answers “how many elements in $[l,r]$ are $\le x$” in $O({\log }^{2}n)$.

Construction

vector<vector<int>> tree_;                      // tree_[node] = sorted elements of its range
 
void build(int node, int l, int r, vector<int>& a) {
    if (l == r) { tree_[node] = {a[l]}; return; }
    int m = (l + r) / 2;
    build(2*node, l, m, a);
    build(2*node+1, m+1, r, a);
    tree_[node].resize(r - l + 1);
    merge(tree_[2*node].begin(), tree_[2*node].end(),
          tree_[2*node+1].begin(), tree_[2*node+1].end(),
          tree_[node].begin());
}

Build is $O(n\log n)$ time and memory — each element appears once per level.

Query

int countLE(int node, int l, int r, int ql, int qr, int x) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr)
        return upper_bound(tree_[node].begin(), tree_[node].end(), x) - tree_[node].begin();
    int m = (l + r) / 2;
    return countLE(2*node, l, m, ql, qr, x) + countLE(2*node+1, m+1, r, ql, qr, x);
}

$O(\log n)$ nodes, each with an $O(\log n)$ binary search → $O({\log }^{2}n)$.

Fractional cascading

Storing, in each node, the position each element maps to in its children removes the repeated binary search — the child’s position follows from the parent’s in $O(1)$. That gives $O(\log n)$ per query.

The bookkeeping is significant and the constant improvement is modest; it is rarely worth writing in a contest, but it is the standard example of the fractional cascading technique.

What it answers

Query	Method
Count of elements $\le x$ in $[l,r]$	upper_bound per node
Count in a value range $[a,b]$ in $[l,r]$	difference of two counts
$k$-th smallest in $[l,r]$	binary search the answer + count, $O({\log }^{3}n)$
Smallest element $\ge x$ in $[l,r]$	lower_bound per node, take the min
Number of distinct values	✘ — use a different structure

The competitors

Structure	Build	Query	Updates	Memory
Merge sort tree	$O(n\log n)$	$O({\log }^{2}n)$	✘	$O(n\log n)$
Merge sort tree + fractional cascading	$O(n\log n)$	$O(\log n)$	✘	$O(n\log n)$
Persistent segment tree	$O(n\log n)$	$O(\log n)$	✘	$O(n\log n)$
Wavelet tree	$O(n\log C)$	$O(\log C)$	✘	$O(n\log C)$ bits
BIT of sorted vectors	$O(n\log n)$	$O({\log }^{2}n)$	✘	$O(n\log n)$
Offline BIT sweep	—	$O(\log n)$ am.	✔	$O(n)$
Mo’s algorithm	—	$O(\sqrt{n})$	✘	$O(n)$
Sqrt decomposition + sorted blocks	$O(n\log n)$	$O(\sqrt{n}\log n)$	✔ (rebuild a block)	$O(n)$

Prefer the offline sweep

If the queries are known in advance — which they nearly always are — sort by value and sweep with a plain BIT over positions. $O((n+q)\log n)$ time, $O(n)$ memory, and it supports point updates. That beats a merge sort tree on every axis.

Persistent segment trees are the right choice when the queries must be online and you need the $k$-th smallest.

Supporting updates

Replacing an element requires re-sorting every node on its root path — $O(n)$ per update in the worst case. If updates are needed:

• Point updates + range count → offline BIT sweep, or a sqrt decomposition with sorted blocks (rebuild one block in $O(B)$).
• Replace the sorted vector in each node with a multiset or a BIT — $O({\log }^{2}n)$ updates but a much worse constant and $O(n\log n)$ memory of node overhead.

Where it is still the right call

The merge sort tree earns its place when you need online range-count-less-than queries, have no update requirement, and want something you can write correctly in ten minutes. It is simple, hard to get wrong, and $O({\log }^{2}n)$ is plenty for $q=10^5$.

See also: Segment Tree · Wavelet Tree · Persistent Structures