Persistent range-distinct counts: keep only the latest position active

Last updated: 5 Oct 20269 min read

tutorial

A persistent range-distinct index keeps one path-copied segment-tree root for each prefix of an immutable incident log. In version r, exactly the latest position before r of each seen code has marker one; earlier occurrences have marker zero. Appending a code clears its prior marker if it has one, sets the new position, and retains all older roots. A query over [l,r) reads root r and sums markers from l through r-1. Every distinct code present in that interval has a latest occurrence in the interval, and no code contributes twice. The tree indexes positions rather than values, so arbitrary hashable incident codes work without value compression. The source log is frozen after construction; an in-place correction would invalidate all later prefix versions.

Operational case

The log [A-47,B-19,A-47,C-61,B-19,D-83] contains three distinct codes in [0,5) and four in [2,6). An empty [3,3) interval returns zero. In [1,4), B-19, A-47, and C-61 each contribute once, so the answer is three. Version five marks the latest B-19 at position four, which still lies inside [0,5); version three marks its older position one instead. Earlier roots remain valid for earlier right boundaries. Using the final root for every query can lose a code whose later duplicate lies to the right of the requested interval.

Working Python program

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

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


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


def set_latest(previous, low, high, position, active):
    if high - low == 1:
        return PositionNode(active)
    middle = (low + high) // 2
    if position < middle:
        left = set_latest(previous.left, low, middle, position, active)
        right = previous.right
    else:
        left = previous.left
        right = set_latest(previous.right, middle, high, position, active)
    return PositionNode(left.count + right.count, left, right)


def count_latest(node, low, high, left, right):
    if right <= low or high <= left:
        return 0
    if left <= low and high <= right:
        return node.count
    middle = (low + high) // 2
    return (count_latest(node.left, low, middle, left, right)
            + count_latest(node.right, middle, high, left, right))


class DistinctIncidentIndex:
    def __init__(self, incident_codes):
        if not incident_codes:
            raise ValueError("at least one incident is required")
        self.length = len(incident_codes)
        self.roots = [empty_positions(0, self.length)]
        last_position = {}
        for position, code in enumerate(incident_codes):
            root = self.roots[-1]
            if code in last_position:
                root = set_latest(root, 0, self.length, last_position[code], 0)
            root = set_latest(root, 0, self.length, position, 1)
            self.roots.append(root)
            last_position[code] = position

    def distinct_count(self, left, right):
        if not 0 <= left <= right <= self.length:
            raise IndexError("range outside incident log")
        return count_latest(self.roots[right], 0, self.length, left, right)


incident_codes = ["A-47", "B-19", "A-47", "C-61", "B-19", "D-83"]
incidents = DistinctIncidentIndex(incident_codes)
print(incidents.distinct_count(0, 5), incidents.distinct_count(2, 6))
print(incidents.distinct_count(3, 3), incidents.distinct_count(1, 4))

Output

3 4
0 3

Time, space, and tradeoff

The empty position tree occupies O(N) nodes for N log entries. Each appended code performs one or two path-copy point assignments, taking O(log N) time and new nodes, so construction is O(N log N) time and retained space. A range count costs O(log N) time and O(log N) recursive stack space. The last-position dictionary uses O(U) extra entries for U distinct codes. A direct set over a short interval costs O(length) time and space and may be preferable when queries are rare. This index counts distinct values, not their identities or frequencies, and has no append operation after its fixed-size tree is built.

Common Mistakes

Do not count every occurrence as one active marker.
Do not query the final version when the requested right boundary is earlier.
Do not clear a previous position in an older shared root.
Do not call this mutable after preprocessing; later roots depend on earlier positions.

Connected lessons

Compare this operation boundary with Successor disjoint sets: skip permanently retired slots, Editable substring fingerprints: join hashes in a segment tree, Sliding medians: expire heap entries by event identity, Ball trees: prune exact nearest-depot search with radius bounds, then complete the audit project and decision quiz.

data structures

range-query-structures