Query Optimization Using Precomputation (tables + lookup)

Precompute + query combines offline tables with online lookup—LCA binary lifting, string hashing with prefix arrays, or static min RMQ via sparse table.

Why this shows up in the real world

GIS layers pre-tile elevation; queries hit tiles only. Compilers precompute dominance frontiers.

Core idea (explained for students)

Build table[k][i] for powers of two jumps or blocks; answer by combining O(log n) precomputed chunks.

Try this in Python

def prefix_mins(a: list[int]) -> list[int]:
    m = []
    cur = None
    for x in a:
        cur = x if cur is None else min(cur, x)
        m.append(cur)
    return m


print(prefix_mins([3, 1, 4, 1, 5]))

Common mistakes

• Memory blowup from storing too many layers without sparse tricks.
• Mixing 0- vs 1-based levels in lifting tables.

Key takeaways

• Verify idempotent combine for your monoid (sum, min, gcd) when splitting queries.
• Start with brute on tiny n to validate table semantics.