算法刷题系列（七）：打表——预计算换取查询效率

算法刷题系列（七）：打表——预计算换取查询效率

如果同一类问题会被查询很多次，而所有查询都落在一个有限范围内，可以考虑先计算整个范围的答案，再通过数组或映射快速查表。

本篇承接前面的位运算与二进制枚举，讨论一种不同的时间/空间取舍：把计算提前做完，换取后续查询更快。我们用“多次判断一个小范围内的整数是否为质数”作为原创例子，并比较预计算、按需计算和记忆化搜索。

一、什么是打表？

“打表”通常指预先生成一张答案表：下标或键表示输入，保存的值表示对应答案。

输入 x ──► table[x] ──► 预先计算好的结果

它适合满足以下条件的问题：

1. 输入范围有限，或者可以从所有查询中确定一个较小的上界。
2. 同一个范围内有多个查询，重复计算会造成明显开销。
3. 答案可以被计算并安全保存到数组、列表或映射中。

预计算并不一定意味着穷举所有可能状态。怎样生成表，要根据问题选择算法；质数表可以用筛法一次处理整个范围，比对每个数分别试除更有效。

二、例子：回答一批质数查询

给定一批整数查询，判断每个 x 是否为质数。假设所有查询都满足 0 <= x <= limit。

如果每个查询都单独做试除，判断一个数 x 需要最多检查到 sqrt(x)，q 次查询的粗略复杂度是：

O(q × sqrt(limit))

当查询很多时，可以先用埃拉托斯特尼筛法生成 0 到 limit 的质数表：

1. 先假设所有大于等于 2 的数都是质数。
2. 从 p = 2 开始，如果 p 仍标记为质数，就把 p 的倍数标记为合数。
3. 只需从 p × p 开始标记，因为更小的倍数已经被更小的质因数处理过。
4. 处理到 p × p > limit 后结束。

表构建完成后，判断 x 是否为质数只需读取 isPrime[x]。

三、为什么从平方开始筛？

以 p = 5 为例，它的倍数中：

10 = 2 × 5
15 = 3 × 5
20 = 4 × 5

这些数已经会被更小的质因数 2 或 3 标记。第一个还需要由 5 标记的倍数是：

25 = 5 × 5

因此从 p × p 开始，可以避免重复工作。

当 p × p 大于 limit 时，所有尚未标记的合数都不可能有一个不超过 sqrt(limit) 的未处理质因数；因此剩下的未标记数都是质数。

四、Java 实现

import java.util.ArrayList;
import java.util.List;

public class PrimeTable {
    public static boolean[] build(int limit) {
        if (limit < 0) {
            throw new IllegalArgumentException("limit must be non-negative");
        }
        if (limit == Integer.MAX_VALUE) {
            throw new IllegalArgumentException(
                "limit is too large for an int-indexed table"
            );
        }

        boolean[] isPrime = new boolean[limit + 1];
        if (limit >= 2) {
            for (int value = 2; value <= limit; value++) {
                isPrime[value] = true;
            }

            for (int p = 2; p <= limit / p; p++) {
                if (!isPrime[p]) {
                    continue;
                }

                for (long multiple = (long) p * p;
                     multiple <= limit;
                     multiple += p) {
                    isPrime[(int) multiple] = false;
                }
            }
        }

        return isPrime;
    }

    public static List<Boolean> answerQueries(
            int[] queries, boolean[] isPrime) {
        List<Boolean> answers = new ArrayList<>();
        for (int query : queries) {
            if (query < 0 || query >= isPrime.length) {
                throw new IllegalArgumentException(
                    "Query is outside the precomputed range: " + query
                );
            }
            answers.add(isPrime[query]);
        }
        return answers;
    }

    public static void main(String[] args) {
        int[] queries = {0, 1, 2, 9, 17};
        boolean[] table = build(20);
        System.out.println(answerQueries(queries, table));
    }
}

输出为：

[false, false, true, false, true]

循环条件使用 p <= limit / p，避免在判断 p * p <= limit 时先发生整数溢出；计算倍数时使用 long，避免 multiple += p 在接近 int 上限时回绕。

数组长度与可用内存仍然有限。如果 limit 极大，分配 limit + 1 个布尔值可能耗尽内存；这时应考虑分段筛法或按需判定，而不是盲目扩大表。

五、Python 实现

def build_prime_table(limit: int) -> list[bool]:
    if limit < 0:
        raise ValueError("limit must be non-negative")

    is_prime = [False] * (limit + 1)
    if limit >= 2:
        is_prime[2:] = [True] * (limit - 1)

        p = 2
        while p <= limit // p:
            if is_prime[p]:
                for multiple in range(p * p, limit + 1, p):
                    is_prime[multiple] = False
            p += 1

    return is_prime

def answer_queries(queries: list[int], is_prime: list[bool]) -> list[bool]:
    answers = []
    for query in queries:
        if query < 0 or query >= len(is_prime):
            raise ValueError(f"query is outside the precomputed range: {query}")
        answers.append(is_prime[query])
    return answers

table = build_prime_table(20)
assert answer_queries([0, 1, 2, 9, 17], table) == [
    False,
    False,
    True,
    False,
    True,
]

is_prime[2:] = [True] * (limit - 1) 将索引 2 到 limit 初始化为 True。当 limit < 2 时跳过初始化，因此空范围和小范围也能正确处理。

六、复杂度分析

筛法预计算 0 到 N 的质数表：

• 预处理时间： O(N log log N)；
• 空间复杂度： O(N)；
• 每次查询： O(1)；
• 回答 q 次查询的总时间： O(N log log N + q)。

这里的 N 是所有查询中的最大值，或题目规定的最大查询范围。

七、预计算、按需计算和记忆化

三种方法都能避免重复工作，但触发计算的时机不同：

方法	何时计算	适合场景	代价
预计算表	提前计算整个范围	查询密集、范围可控	可能计算很多用不到的输入，占用整段范围的空间
按需计算	每次查询单独计算	查询少、输入分散	相同输入反复查询时会重复计算
记忆化	第一次遇到某个输入时计算并缓存	状态空间大但实际访问集中	需要缓存管理；若最终几乎访问全部状态，收益可能有限

打表并不总是最快或最省空间。若只有一两个查询，对每个数单独判定可能更简单；如果查询范围巨大但实际只访问少量值，按需计算更合适。

八、常见错误与适用边界

1. 把表的下标范围想当然：查询超出预计算范围时应明确处理，不能越界或默认返回答案。
2. 忘记 0 和 1 不是质数：它们必须保持为 false。
3. 从 2p 开始重复标记：结果仍可能正确，但会做额外工作；从 p² 开始更高效。
4. 预计算过大的范围：表可能占用大量内存，甚至无法构建。
5. 忽略查询密度：只查少数分散值时，构造全范围表可能比按需计算更贵。
6. 把经验规律当证明：如果打表是为了观察规律并寻找公式，表只能提供线索；最终仍要证明观察到的规律覆盖所有输入。
7. 表内容和规则版本不一致：如果结果依赖配置、环境或数据更新，缓存必须有清晰的失效与重建策略。

九、与后续主题的连接

二进制枚举把有限集合中的每一种选择都列出来；打表则把有限输入范围的结果提前算好。两者都依赖“状态空间有限”，但目的不同：

• 枚举关注遍历所有候选状态；
• 打表关注保存输入到答案的映射；
• 记忆化搜索只保存真正访问过的状态。

下一篇将学习表达式计算：输入不再是单个数，而是由数字、运算符和括号构成的字符串，需要用栈或递归结构按照语法求值。

小结

打表通过预处理有限范围的答案，把后续查询转成快速查表。是否值得打表，要比较范围大小、查询次数、实际访问密度和内存限制。质数筛法展示了如何一次性处理整个范围，而不是对每个查询重复试除。