GESP 八级 · GESP 202603 C++ 八级 第 22 题

使用倍增法预处理区间最值问题时，预处理的时间复杂度为 $O(n \log n)$，查询的时间复杂度为 $O(1)$。（ ）

判断正误题需注意绝对化表述（"一定""必须""只能"等）往往是错误的。

判断题中注意"一定""总是""所有""唯一"等绝对化表述通常是错误的。但也要结合具体知识点判断。

【考点】倍增法｜RMQ查询｜时间复杂度分析

解题思维：看到"倍增法预处理区间最值"，先想到倍增法核心结构：数组 up[i][j] 存储区间 [i, i + 2^j] 的最值。预处理时，对每个 i 和 j (1 ≤ j ≤ log n) 递推计算，总格点数为 n log n，故时间复杂度 O(n log n)。查询时，将区间长度拆成 2 的幂次，每个幂次直接查表，合并结果，查询时间 O(1)。这类倍增题通法：预处理 O(n log n) 换查询 O(1)，适用于任何可分解为 2^j 子问题的场景。

陷阱拆解：选项 B 是经典陷阱。命题人故意把预处理和查询时间混在一起考，想看你是否清楚倍增法的代价：预处理 O(n log n) 是为了换取查询 O(1)。若你只背结论，看到"预处理"就以为 O(n)，看到"查询"就以为 O(log n)，就会选错。最阴险的细节在于"区间最值"——倍增法不仅用于 LCA，也用于 RMQ，但 RMQ 的预处理确实是 O(n log n)。

反命题思维：若把题改成"预处理 O(n) 查询 O(1)"，答案就变错；改成"预处理 O(n log n) 查询 O(log n)"，答案也错。刷到类似倍增题时，先问自己：命题人想考我是否分清预处理和查询的代价，还是想考我是否知道倍增法在 RMQ 上的应用？