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

Segment-tree stabbing indexes: list intervals active at one point

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

An interval stabbing index answers which stored intervals contain a query coordinate. Over a fixed integer universe [0,U), this segment tree places each half-open interval in a small set of canonical tree nodes whose ranges exactly cover it. A point query follows one root-to-leaf path and collects interval IDs in buckets along that path. Each stored interval appears once on that path if it contains the queried point, and nowhere on that path otherwise. Removal uses the original interval endpoints to remove its ID from the same canonical buckets. The example stores one interval per task ID, supports add and remove, and rejects coordinates outside its configured universe.

Operational case

M-19 covers [19,61) and M-47 covers [47,83). At time 50, both IDs are active; at 83 neither is active because right endpoints are excluded. Removing M-19 leaves only M-47 active at 50. The ID table prevents accidentally adding a second range under one identifier without first removing the old one. Querying an integer outside [0,128) is an error, not an empty result, because the tree has no leaf there. This structure keeps individual interval IDs, unlike a disjoint interval union that retains only the covered set.

Working Python program

python
class StabbingWindows:
    def __init__(self, universe_size):
        if universe_size < 1:
            raise ValueError("universe must be positive")
        self.size = universe_size
        self.buckets = [set() for _ in range(4 * universe_size)]
        self.intervals = {}

    def _visit_cover(self, node, low, high, start, end, task_id, adding):
        if end <= low or high <= start:
            return
        if start <= low and high <= end:
            if adding:
                self.buckets[node].add(task_id)
            else:
                self.buckets[node].remove(task_id)
            return
        middle = (low + high) // 2
        self._visit_cover(2 * node, low, middle, start, end, task_id, adding)
        self._visit_cover(2 * node + 1, middle, high, start, end, task_id, adding)

    def add(self, task_id, start, end):
        if task_id in self.intervals:
            raise ValueError("duplicate task ID")
        if not 0 <= start < end <= self.size:
            raise ValueError("interval outside universe")
        self._visit_cover(1, 0, self.size, start, end, task_id, True)
        self.intervals[task_id] = start, end

    def remove(self, task_id):
        start, end = self.intervals.pop(task_id)
        self._visit_cover(1, 0, self.size, start, end, task_id, False)

    def active_at(self, instant):
        if not 0 <= instant < self.size:
            raise ValueError("instant outside universe")
        node, low, high = 1, 0, self.size
        active = set()
        while True:
            active.update(self.buckets[node])
            if high - low == 1:
                return sorted(active)
            middle = (low + high) // 2
            if instant < middle:
                node, high = 2 * node, middle
            else:
                node, low = 2 * node + 1, middle


if __name__ == "__main__":
    schedule = StabbingWindows(128)
    schedule.add("M-19", 19, 61)
    schedule.add("M-47", 47, 83)
    print(schedule.active_at(50), schedule.active_at(83))
    schedule.remove("M-19")
    print(schedule.active_at(50))

Output

Output
['M-19', 'M-47'] []
['M-47']

Time, space, and tradeoff

An add or remove touches O(log U) canonical nodes in a binary tree over U integer positions, with expected set operations for each bucket. A point query traverses O(log U) nodes, gathers K matching IDs, then sorts them in O(K log K); it uses O(K) output memory. The allocated Python bucket array has O(U) entries before any interval arrives, and M stored intervals contribute O(M log U) worst-case bucket references. A large sparse coordinate universe would warrant compression or a sparse node tree. This index reports active IDs, while a range-add segment tree usually aggregates numeric values instead.

Common Mistakes

  • Do not include an interval's right endpoint in a half-open point query.
  • Do not lose original endpoints needed to remove canonical bucket entries.
  • Do not use the index outside its configured universe.
  • Do not confuse covered length with the list of interval identities.

Connected lessons

Compare its query and update boundary with LZ78 phrase tries: emit dictionary index and next symbol, Huffman trees: assign prefix codes from symbol frequencies, Condensation DAGs: compress directed cycles before path queries, then complete the structure audit and decision quiz.

data structures
range-query-structures
Storage details