Sparse tables: range minimum and LCA in O(1)

A sparse table answers the minimum of any range of fixed data in O(1): it stores the minimum of every block whose length is a power of two, and any range is covered by two such blocks that may overlap, which a minimum allows. The same table answers lowest-common-ancestor questions on a fixed tree in O(1) each, through an Euler tour of the tree. This lesson works both on two original problems: the lowest temperature of a finished season, and the deepest folder that holds two files.

Two problems on data that never changes

Problem A: the coldest span of a season. A weather station’s season is over: lows[d] is the lowest temperature of day d, in whole degrees, possibly negative. Answer many questions “what was the lowest temperature from day l to day r?”. With lows = [4, 2, 7, -1, 3, -1, 6, 5], days 0 to 7 give −1, days 0 to 2 give 2, days 4 to 7 give −1 and days 6 and 7 give 5.

Problem B: the deepest common folder. A shared drive has n folders; parent[v] holds folder v, and the root has −1. For a pair of folders, find the deepest folder that contains both, their lowest common ancestor (LCA), and the number of cd steps from one to the other. In the tree of the diagram below, drafts and specs meet in docs, 3 steps apart; ui and tests in src; drafts and ui only in the root; and app contains ui itself.

Limits for both: up to 200,000 values or folders and 200,000 questions.

The brute force: scan the span, walk up the tree

For A, scan the days of each span. For B, walk the deeper folder up to the other’s depth, then both up together until they meet:

"""Both problems the slow way, with the work counted: scan every span of days, and walk up from both folders."""
import random

lows = [4, 2, 7, -1, 3, -1, 6, 5]
spans = [(0, 7), (0, 2), (4, 7), (6, 7)]
print("A: daily lows", lows)
print("   lowest of each span:", [min(lows[a : b + 1]) for a, b in spans])

parent = [-1, 0, 0, 1, 1, 2, 2, 5, 3]  # 0 is the root folder
names = ["/", "docs", "src", "notes", "specs", "app", "tests", "ui", "drafts"]


def depth_of(parent):
    depth = [0] * len(parent)
    for v in range(len(parent)):  # here every parent has a smaller number than its child
        if parent[v] >= 0:
            depth[v] = depth[parent[v]] + 1
    return depth


def walk_up(parent, depth, a, b):
    steps = 0
    while depth[a] > depth[b]:
        a, steps = parent[a], steps + 1
    while depth[b] > depth[a]:
        b, steps = parent[b], steps + 1
    while a != b:
        a, b, steps = parent[a], parent[b], steps + 2
    return a, steps


depth = depth_of(parent)
print("B: deepest common folder of each pair")
for a, b in [(8, 4), (7, 6), (8, 7), (5, 7), (4, 4)]:
    print(f"   {names[a]} and {names[b]}: {names[walk_up(parent, depth, a, b)[0]]}")

rng = random.Random(6)
for shape, n in (("random tree", 20_000), ("chain", 3_000)):
    parent = [-1] + [rng.randrange(v) if shape == "random tree" else v - 1 for v in range(1, n)]
    depth = depth_of(parent)
    steps = sum(walk_up(parent, depth, rng.randrange(n), rng.randrange(n))[1] for _ in range(n))
    print(f"{shape} of {n:,} folders, {n:,} questions: {steps:,} steps up, {steps / n:,.1f} a question")
print("a chain of 200,000 folders: about 200,000 / 3 = 66,667 steps a question, so about 1.3e+10 for 200,000"
      " questions (estimated)")

A: daily lows [4, 2, 7, -1, 3, -1, 6, 5]
   lowest of each span: [-1, 2, -1, 5]
B: deepest common folder of each pair
   drafts and specs: docs
   ui and tests: src
   drafts and ui: /
   app and ui: app
   specs and specs: specs
random tree of 20,000 folders, 20,000 questions: 351,966 steps up, 17.6 a question
chain of 3,000 folders, 3,000 questions: 2,990,113 steps up, 996.7 a question
a chain of 200,000 folders: about 200,000 / 3 = 66,667 steps a question, so about 1.3e+10 for 200,000 questions (estimated)

A scan of a random span reads about a third of the season, about 66,000 days at the limit, for each question. Walking up costs the depth of the tree: 17.6 steps a question on a random tree, but about n / 3 on a chain, where every folder holds the next. A chain of 200,000 folders needs about 1.3 × 10¹⁰ steps for 200,000 questions.

What to notice

Nothing changes after the data is read, so slow preparation is fine if every question becomes cheap. For A, a minimum does not mind counting a day twice, so two overlapping blocks of a power-of-two length can cover any span. For B, write down the folders in the order a depth-first walk visits them, each time it is at one: between the first visits of two folders, the walk stays inside their LCA’s subtree and passes the LCA itself, so the shallowest folder there is the answer, which is problem A on the tour’s depths.

The main alternative for problem B is binary lifting, which stores each folder’s ancestors 1, 2, 4 and more levels up and answers a question in O(log n) steps.

The sparse table, step by step Pro: opens with a Pro, Premium or Ultimate pass