Precomputation Strategy (pay once, query many)

Precomputation pays once to answer many queries—prefix sums, sparse tables, factor tables for number theory. Choose what is static in the problem statement.

Why this shows up in the real world

Search engines build inverted indexes overnight. Games bake navigation meshes at build time.

Core idea (explained for students)

Identify immutable structure, build auxiliary arrays in O(n) or O(n log n), answer queries in O(1)/O(log n).

Try this in Python

def precompute_divisors_upto(n: int) -> list[list[int]]:
    divs: list[list[int]] = [[] for _ in range(n + 1)]
    for d in range(1, n + 1):
        for m in range(d, n + 1, d):
            divs[m].append(d)
    return divs


print(precompute_divisors_upto(12)[12])

Common mistakes

• Precomputing exponential tables when only a narrow range is queried.
• Stale precompute when inputs can change—need invalidation layer.

Key takeaways

• Match precompute granularity to query types (per-node vs per-edge).
• Version your precomputed artifacts in production systems.