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

Persistent subarray ranks: subtract prefix frequency trees

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

A persistent order-statistic index keeps one frequency segment-tree root after each prefix of an immutable array. Values are first compressed into sorted ranks. Inserting the next value copies only the nodes on its rank path; all unaffected nodes remain shared with the previous root. A half-open query [l,r) subtracts counts in root l from corresponding counts in root r. At each value split, that difference gives the number of requested elements in the lower-ranked half. Descend left if the requested one-based rank fits there; otherwise subtract that count and descend right. Duplicate values increment a leaf count, so repeated priorities occupy consecutive order positions rather than vanishing as they would in a set. Roots represent insertion history, not editable versions of arbitrary array positions.

Operational case

Shipment priorities [47,19,61,29,19,83,37] produce eight roots, including the empty prefix. In [1,6), the sorted priorities are [19,19,29,61,83], so rank three returns 29. Across the complete array, rank six returns 61. In [2,5), rank two is 29. The left root must be subtracted from the right root at every branch; using only the right root silently includes earlier shipments. A request for rank zero, a rank above the interval length, or an empty interval is rejected. This index returns a value, not which duplicate shipment record supplied it.

Working Python program

python
from bisect import bisect_left


class CountNode:
    __slots__ = ("count", "left", "right")

    def __init__(self, count=0, left=None, right=None):
        self.count = count
        self.left = left
        self.right = right


def add_count(previous, low, high, rank):
    if high - low == 1:
        return CountNode(previous.count + 1)
    middle = (low + high) // 2
    if rank < middle:
        changed_left = add_count(previous.left, low, middle, rank)
        return CountNode(previous.count + 1, changed_left, previous.right)
    changed_right = add_count(previous.right, middle, high, rank)
    return CountNode(previous.count + 1, previous.left, changed_right)


def empty_counts(low, high):
    if high - low == 1:
        return CountNode()
    middle = (low + high) // 2
    return CountNode(0, empty_counts(low, middle), empty_counts(middle, high))


class ShipmentRankIndex:
    def __init__(self, priorities):
        if not priorities:
            raise ValueError("at least one priority is required")
        self.values = sorted(set(priorities))
        self.roots = [empty_counts(0, len(self.values))]
        for priority in priorities:
            rank = bisect_left(self.values, priority)
            self.roots.append(add_count(self.roots[-1], 0, len(self.values), rank))

    def kth(self, left, right, position):
        if not 0 <= left < right < len(self.roots):
            raise IndexError("range must be nonempty and inside the array")
        if not 1 <= position <= right - left:
            raise ValueError("position is outside the range")
        before = self.roots[left]
        after = self.roots[right]
        low, high = 0, len(self.values)
        while high - low > 1:
            middle = (low + high) // 2
            left_count = after.left.count - before.left.count
            if position <= left_count:
                before, after, high = before.left, after.left, middle
            else:
                position -= left_count
                before, after, low = before.right, after.right, middle
        return self.values[low]


shipment_priorities = [47, 19, 61, 29, 19, 83, 37]
priority_index = ShipmentRankIndex(shipment_priorities)
print(priority_index.kth(1, 6, 3))
print(priority_index.kth(0, 7, 6))
print(priority_index.kth(2, 5, 2))

Output

Output
29
61
29

Time, space, and tradeoff

Let N be array length and U the number of distinct values. Sorting and compression cost O(N log N) time. The empty count tree occupies O(U) nodes; N path-copy insertions cost O(N log U) time and new nodes, making total retained space O(U + N log U). Each valid kth query takes O(log U) time and O(1) auxiliary space in the iterative descent. Python node objects carry more memory than packed integer arrays. A static wavelet tree can answer related ranks with another layout; a single sorted copy cannot isolate an arbitrary subarray without extra indexing. Rebuilding is required after changing the source array.

Common Mistakes

  • Do not forget the left-prefix subtraction at each child.
  • Do not discard duplicate values during rank counting.
  • Do not use zero-based k with this one-based API.
  • Do not mutate a node shared by older prefix roots.

Connected lessons

Compare this operation boundary with Maximum-subarray segment trees: preserve the crossing burst, Li Chao interval offers: limit each line to its valid minutes, All-one frequency buckets: increment, decrement, and read both extremes, Patricia binary routing: compress chains without losing prefix matches, then complete the audit project and decision quiz.

data structures
range-query-structures
Storage details