Segment Tree stores one combined value per
node — the minimum, the sum, whatever the operation is — and throws away everything else about the
range it covers. A Merge Sort Tree is the same shape, built over the same ranges,
but every node keeps the entire sorted contents of its range instead of collapsing it to
one number. That answers a question no single associative combine can: "how many elements in
[l, r] are ≤ x?" — count the whole range with one binary search per
node touched, no scan required. The build step is exactly the merge half of merge sort, run
bottom-up: a leaf's sorted array is just its one value, and every internal node's sorted array is
its two children's arrays merged together, the same linear-time merge merge sort already does
between subarrays.
This is also the question Wavelet Tree
answers, with a different mechanism entirely — a wavelet tree splits its O(log σ)
levels by value (which half of the alphabet) and answers in time independent of the
sequence length, using one bit per element per level plus rank-support tables. A Merge Sort Tree
splits by position, the ordinary segment-tree way, and pays for its plain-arrays simplicity
in space: every one of its O(log n) levels holds a full copy of up to n
elements, where a wavelet tree holds one bit. Reach for this one when the alphabet is large or
unbounded (a wavelet tree's O(log σ) stops being cheap once σ
is comparable to n anyway) or when plain sorted arrays and binary search are simply
easier to get right than bit-vector rank tables — not as a default upgrade.
Eight values, indexed 0 through 7, deliberately including a repeat (two 3s) to
make the binary search boundary visible. Press Step or Run to
watch the tree get built bottom-up: each leaf holds its one value, and every parent's row is its two
children's rows merged into one sorted list — watch node [0,7] at the root end up
holding all eight values in order. Then pick a range [l, r] and a threshold
x and press Query to count how many values in that range are
≤ x: the walk visits at most O(log n) canonical nodes
(solid highlight) whose range sits entirely inside [l, r] — each gets one binary search,
with matching values (≤ x) picked out directly in its row — while nodes entirely
outside [l, r] (faded) are skipped without a single comparison, and nodes only partly
overlapping (dashed) hand off to their own two children instead of being searched directly.
Build is post-order: a leaf [i,i] is trivially sorted (one element),
and every internal node [lo,hi] waits for both children to finish, then merges their
two already-sorted arrays in O(hi - lo + 1) time — the standard two-pointer merge, no
sorting from scratch. Because every one of the O(log n) levels partitions the same
n underlying elements into disjoint ranges, each level's merges do O(n)
total work, for O(n log n) across the whole build. Sorting each node's slice
independently instead of merging children would still be correct, just slower: O(k log k)
per node of size k, summing to O(n log² n) across a level — the merge
isn't required for correctness, only for hitting the same O(n log n) bound merge sort
itself gets.
Query reuses the identical canonical-node decomposition Segment Tree already established: recurse from the
root, and at every node compare its own range against the query range [l, r]. A node
entirely outside [l, r] contributes nothing and stops the recursion immediately. A node
entirely inside [l, r] is canonical — its whole sorted array is fair game, so
one binary search (upper_bound(x), counting how many entries are ≤ x)
gives its exact contribution without looking at a single other node. Anything else overlaps only
partially, so neither child can be skipped — recurse into both. The same argument that bounds a plain
segment tree's range query to O(log n) nodes applies unchanged here, since it only
depends on how [l, r] tiles against the tree's ranges, not on what each node stores —
the difference is that each of those O(log n) canonical nodes now costs
O(log n) (a binary search into its own array) instead of O(1) (reading one
precombined value), for O(log² n) total instead of a plain segment tree's
O(log n).
function merge(a, b) {
const out = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]);
while (i < a.length) out.push(a[i++]);
while (j < b.length) out.push(b[j++]);
return out;
}
function build(values, lo, hi) {
if (lo === hi) return { lo, hi, arr: [values[lo]], left: null, right: null };
const mid = (lo + hi) >> 1;
const left = build(values, lo, mid);
const right = build(values, mid + 1, hi);
return { lo, hi, arr: merge(left.arr, right.arr), left, right };
}
// count of entries <= x in a sorted array — upper_bound / bisect_right
function upperBound(arr, x) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] <= x) lo = mid + 1; else hi = mid;
}
return lo;
}
// count of entries <= x within array positions [l, r], inclusive
function countLE(node, l, r, x) {
if (node.hi < l || r < node.lo) return 0; // fully outside — skip
if (l <= node.lo && node.hi <= r) return upperBound(node.arr, x); // fully inside — canonical
return countLE(node.left, l, r, x) + countLE(node.right, l, r, x); // partial — recurse both
}A strict-less-than binary search undercounts every time a value equals
x — wrong 32.9% of the time. The natural-looking off-by-one: search for the
first index where arr[mid] < x stops holding (i.e. lower_bound, "count
strictly less than x") instead of arr[mid] ≤ x (upper_bound,
"count less than or equal to x"). It compiles, it terminates, and on an array with no
value exactly equal to x it happens to agree with the correct version — which is exactly
what makes it dangerous, since small hand-tested examples chosen without a repeated boundary value
won't catch it. Stress-tested directly: 200,000 trials (random arrays of 1-30 small integers, random
[l,r] and x) against a brute-force linear scan. The reference
implementation above matched brute force in all 200,000. The strict-less-than version disagreed in
65,740 — 32.9% of the time, every single mismatch an undercount by exactly the
number of entries in range equal to x.
An off-by-one on the out-of-range test silently drops boundary elements — wrong 45.4% of
the time. A second, more damaging mistake: writing the "fully outside" check as
node.hi ≤ l || r ≤ node.lo instead of the correct
node.hi < l || r < node.lo. It looks like a harmless boundary tightening, but it
wrongly treats a node whose hi lands exactly on l (or whose lo
lands exactly on r) as fully outside the query, when that node's last (or first) index
is a real, legitimate member of [l, r]. Every query whose range boundary lines up with a
tree node's own boundary silently loses that one index. Stress-tested the same way, same 200,000
trials: the reference implementation 0 mismatches, this version wrong in
90,894 — 45.4% of the time — worse than the first bug because query ranges that
happen to align with a node boundary are common, not a rare edge case, on any array whose size is a
power of two or close to one.
Competitive programming, almost exclusively — "count values ≤ x in
[l, r]" and its sibling "find the k-th smallest value in [l, r]"
(answered by driving countLE as the monotonic predicate inside Binary Search on Answer, over the value range
rather than the array itself, for O(log(maxVal) · log² n) per query) are
common enough problem shapes that "sorted arrays plus binary search, no bit tricks" earns its keep
purely as the version that's fastest to get right under contest time pressure. Production systems
needing this same range-rank question at scale reach for Wavelet Tree's tighter space instead, or a
value-indexed Persistent Segment Tree
(one version inserted per array prefix, queried by subtracting two versions) — the same
O(log² n) query time as this page, but O(n log n) space reached
through structural sharing rather than n log n literal copied array entries, a real
constant-factor win at scale even though the asymptotic space bound reads the same on paper.
Build: O(n log n) — each of the O(log n) levels merges
disjoint ranges covering all n elements combined, O(n) work per level.
Query: O(log² n) — the query touches the same
O(log n) canonical nodes a plain segment tree range query would, but each now costs
O(log n) for its own binary search instead of O(1) for a precombined value.
Space: O(n log n) — every element is copied into the sorted array of
every ancestor node on its root-to-leaf path, O(log n) ancestors deep.
No updates. This reference implementation never changes a value once built —
unlike Segment Tree, where updating one leaf only
touches O(log n) nodes on its root path, updating one value here would need re-merging
every one of those same O(log n) ancestor arrays from scratch (each one a full sorted
copy of its range, not a single combined number that can be patched in place), for
O(n) worst case at the root. Treat this structure as built once over a static array, the
same static-only territory Sparse Table and Wavelet Tree occupy on this site, not as a drop-in
replacement for a plain segment tree.
This site's guide, Choosing a Range Query Structure, sets this entry aside the same way it already sets aside Wavelet Tree — a question about values within a position range, not a single running combined answer over one.