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

Sparse coordinate segment tree: allocate only visited paths

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

A sparse coordinate segment tree stores aggregate nodes only on paths touched by point assignments. Its logical coordinate space can be enormous without allocating an array proportional to that space. Each node covers a half-open interval and keeps the sum of its descendants. Missing children represent zero. The meter index also keeps a small map of assigned values, so an assignment computes the difference from the previous reading instead of accidentally adding the new value twice. The public range convention is [start, stop); empty intervals return zero. The root exists even when no meter has a nonzero reading.

Operational case

The span has 2^40 possible positions. Assign 19 at coordinate 47 and 26 at a position just above the halfway point. Reassign position 47 to 52. A query over [0, 100) returns 52, and the whole span returns 78. Assigning zero at 47 makes the first query zero again. This sparse representation does not physically prune now-empty paths in the shown code; long-running workloads that cycle through many distinct positions can retain nodes after their readings return to zero. A separate pruning pass or a different index may be needed when that pattern dominates.

Working Python program

python
"""Point assignments and half-open sums over a huge, mostly empty coordinate span."""

from dataclasses import dataclass


@dataclass
class SumNode:
    total: int = 0
    left: "SumNode | None" = None
    right: "SumNode | None" = None


class SparseMeterIndex:
    def __init__(self, coordinate_limit: int):
        if coordinate_limit <= 0:
            raise ValueError("coordinate_limit must be positive")
        self.coordinate_limit = coordinate_limit
        self.root = SumNode()
        self.values: dict[int, int] = {}

    def assign(self, meter_position: int, reading: int) -> None:
        if not 0 <= meter_position < self.coordinate_limit:
            raise IndexError(meter_position)
        previous = self.values.get(meter_position, 0)
        difference = reading - previous
        if difference == 0:
            return
        if reading:
            self.values[meter_position] = reading
        else:
            self.values.pop(meter_position, None)
        node = self.root
        low, high = 0, self.coordinate_limit
        while True:
            node.total += difference
            if high - low == 1:
                break
            middle = (low + high) // 2
            if meter_position < middle:
                if node.left is None:
                    node.left = SumNode()
                node, high = node.left, middle
            else:
                if node.right is None:
                    node.right = SumNode()
                node, low = node.right, middle

    def sum_between(self, start: int, stop: int) -> int:
        if not 0 <= start <= stop <= self.coordinate_limit:
            raise IndexError((start, stop))

        def visit(node: SumNode | None, low: int, high: int) -> int:
            if node is None or stop <= low or high <= start:
                return 0
            if start <= low and high <= stop:
                return node.total
            middle = (low + high) // 2
            return visit(node.left, low, middle) + visit(node.right, middle, high)

        return visit(self.root, 0, self.coordinate_limit)


meter_index = SparseMeterIndex(1 << 40)
meter_index.assign(47, 19)
meter_index.assign((1 << 39) + 61, 26)
meter_index.assign(47, 52)
print(meter_index.sum_between(0, 100))
print(meter_index.sum_between(0, 1 << 40))
meter_index.assign(47, 0)
print(meter_index.sum_between(0, 100))

Output

Output
52
78
0

Time, space, and tradeoff

With coordinate limit U, a point assignment follows O(log U) nodes and a range sum visits O(log U) boundary branches in the standard segment-tree decomposition. The map lookup is expected O(1). If M distinct positions have ever been assigned a changed value, path allocation can use O(M log U) nodes in the worst case, even when the current nonzero count is smaller. The recursive query consumes O(log U) call-stack space. This is not a compressed coordinate index: unlike a Fenwick tree over sorted known coordinates, it accepts unseen positions online, while paying pointer and Python object overhead for each allocated node.

Common Mistakes

  • Do not treat a point assignment as an increment; subtract the previous value first.
  • Do not mix inclusive and half-open range endpoints.
  • Do not claim memory falls when a value returns to zero; this code retains its path.
  • Do not allocate a full array for a 2^40 span with only a few active positions.

Connected lessons

Apply the invariant in the sparse readings and task constraints project, then check the operations quiz.

Li Chao trees: minimum linear tariff at a chosen quantity extends this range-query decision.

Li Chao interval offers: limit each line to its valid minutes examines a related structure with a different operation boundary.

data structures
range-query-structures
Storage details