Disjoint sparse tables: immutable sums with constant-time queries

Last updated: 5 Oct 20269 min read

tutorial

A disjoint sparse table prepares an immutable sequence for associative range queries. At every binary scale, it computes suffix sums on the left of a split and prefix sums on the right. For a non-singleton interval, the highest bit where its first and last positions differ identifies one split between them. The corresponding suffix and prefix cover the requested interval exactly once, with no overlap. That matters for addition: an ordinary sparse-table trick that overlaps two intervals works for idempotent minimum, but double-counts values under sum. The public method uses half-open positions and returns zero for an empty interval by explicit API choice.

Operational case

The seven scan totals are 23, 47, 19, 61, 38, 52, and 29. The sum over [1, 6) is 217, across several binary split sizes. A one-value query [3, 4) returns 61 directly, since there is no differing endpoint bit to select. The empty query [2, 2) returns zero. Use unequal values so a duplicated contribution would change the expected result, and test intervals that both cross and stay within the largest split. Any later edit to a reading invalidates the prepared layers and calls for a rebuild.

Working Python program

class DisjointSumTable:
    def __init__(self, readings):
        self.values = list(readings)
        self.layers = []
        size = len(self.values)
        for level in range(max(0, (size - 1).bit_length())):
            half = 1 << level
            width = half * 2
            layer = [0] * size
            for block_start in range(0, size, width):
                middle = min(block_start + half, size)
                block_stop = min(block_start + width, size)
                if middle > block_start:
                    layer[middle - 1] = self.values[middle - 1]
                    for position in range(middle - 2, block_start - 1, -1):
                        layer[position] = self.values[position] + layer[position + 1]
                if middle < block_stop:
                    layer[middle] = self.values[middle]
                    for position in range(middle + 1, block_stop):
                        layer[position] = layer[position - 1] + self.values[position]
            self.layers.append(layer)

    def sum_between(self, start, stop):
        if not 0 <= start <= stop <= len(self.values):
            raise IndexError("invalid half-open reading range")
        if start == stop:
            return 0
        if stop - start == 1:
            return self.values[start]
        level = (start ^ (stop - 1)).bit_length() - 1
        return self.layers[level][start] + self.layers[level][stop - 1]


if __name__ == "__main__":
    table = DisjointSumTable([23, 47, 19, 61, 38, 52, 29])
    print("window=", table.sum_between(1, 6), sep="")
    print("single=", table.sum_between(3, 4), sep="")
    print("empty=", table.sum_between(2, 2), sep="")

Output

window=217
single=61
empty=0

Time, space, and tradeoff

For N values, each of O(log N) layers fills at most N cells, giving O(N log N) preprocessing time and O(N log N) stored cells. A query performs bounds checks, one highest-differing-bit calculation, and two array reads, which is O(1) under a fixed-width word model. With arbitrary-precision integers, the bit and sum operations also depend on operand size. For query-only sums, a prefix-sum array is simpler, uses O(N) memory, and also answers in O(1); disjoint tables matter when the associative operation lacks a cheap inverse. This sum example makes the disjoint-cover invariant inspectable, not a claim that it beats prefix sums in practice.

Common Mistakes

Do not overlap the two halves when the operation is addition.
Do not compute a split level for a singleton interval.
Do not mutate the source values after building the layers.
Do not choose this larger index for ordinary static sums without comparing a prefix array.

Connected lessons

Compare its contract with Square-root blocks: update one capacity and sum a range, Merge-sort trees: count readings below a threshold in one interval, Li Chao trees: minimum linear tariff at a chosen quantity, then apply the range workload project and check the range-index quiz.

data structures

range-query-structures