Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Merge-sort trees: count readings below a threshold in one interval

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A merge-sort tree overlays a binary interval tree on an immutable array. Each node retains a sorted copy of the values in its interval. To count readings at most a threshold inside [start, stop), the query partitions that range into fully covered nodes and binary-searches each node's sorted run. Equal values are counted individually; bisect-right is the boundary that includes the threshold itself. The structure preserves positions through its interval tree while retaining value order locally inside each node. It answers a two-dimensional question involving both position and value, which an ordinary prefix sum cannot answer without another restriction.

Operational case

The stored sensor readings are 41, 18, 41, 73, 26, 55, and 12. In positions [1, 6), three readings are at most 41: 18, 41, and 26. Across the full array, two readings are strictly below 26, which the program expresses as at most 25. The duplicate 41 matters: when a selected interval contains both copies, both must count. A zero-length interval counts zero, including in an empty index. The index is a snapshot; if an old reading changes, this implementation rebuilds rather than patching sorted runs along a path.

Working Python program

python
from bisect import bisect_right
from heapq import merge


class ThresholdCountIndex:
    def __init__(self, readings):
        self.size = len(readings)
        self.nodes = [[] for _ in range(max(1, 4 * self.size))]
        if self.size:
            self._build(1, 0, self.size, readings)

    def _build(self, node, left, right, readings):
        if right - left == 1:
            self.nodes[node] = [readings[left]]
            return
        middle = (left + right) // 2
        self._build(2 * node, left, middle, readings)
        self._build(2 * node + 1, middle, right, readings)
        self.nodes[node] = list(merge(self.nodes[2 * node], self.nodes[2 * node + 1]))

    def count_at_most(self, start, stop, threshold):
        if not 0 <= start <= stop <= self.size:
            raise IndexError("invalid half-open reading range")
        if start == stop:
            return 0
        return self._count(1, 0, self.size, start, stop, threshold)

    def _count(self, node, left, right, start, stop, threshold):
        if stop <= left or right <= start:
            return 0
        if start <= left and right <= stop:
            return bisect_right(self.nodes[node], threshold)
        middle = (left + right) // 2
        return self._count(2 * node, left, middle, start, stop, threshold) + self._count(2 * node + 1, middle, right, start, stop, threshold)


if __name__ == "__main__":
    index = ThresholdCountIndex([41, 18, 41, 73, 26, 55, 12])
    print("at-most-41=", index.count_at_most(1, 6, 41), sep="")
    print("under-26=", index.count_at_most(0, 7, 25), sep="")
    print("empty=", index.count_at_most(4, 4, 41), sep="")

Output

Output
at-most-41=3
under-26=2
empty=0

Time, space, and tradeoff

For N readings, each tree level stores N copied values. Construction takes O(N log N) time and O(N log N) space. A query covers O(log N) nodes and performs O(log N) binary search at each, giving O(log squared N) time. The Python implementation also pays for list objects and merged copies, so memory is material. A wavelet tree can answer related rank and selection queries with different storage and traversal tradeoffs. A simple sort of the selected slice costs O(K log K) for a range of K readings and may win when queries are rare. This lesson's index has no incremental update method.

Common Mistakes

  • Use bisect-right for an inclusive at-most threshold; bisect-left excludes equality.
  • Do not discard duplicate readings when merging runs.
  • Do not assume the sorted root preserves original positions by itself.
  • Do not advertise point updates for this immutable implementation.

Connected lessons

Compare its contract with Square-root blocks: update one capacity and sum a range, Disjoint sparse tables: immutable sums with constant-time queries, Li Chao trees: minimum linear tariff at a chosen quantity, then apply the range workload project and check the range-index quiz.

Mo ordering: count distinct scan codes across an offline query batch extends this operation choice.

Range-majority indexes: verify a candidate before returning it adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details