OI-wiki 竞赛技巧打表与分段打表全解析【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki打表Precomputation / Table Lookup是算法竞赛中一种非常实用的退路型技巧当题目数据范围小到可以直接枚举或标准解法难以在赛时推出来时提前把所有答案算好、存进代码里直接输出。本文基于 OI-wiki 的 竞赛技巧·打表 文档完整讲解朴素打表的适用边界、用分块思想实现的分段打表分段打表及其复杂度原理并结合仓库内 分块思想、分块参考实现 与 constexpr 编译期存储 给出可落地的实战方案。读完本文你将掌握判断什么题能打表、该朴素打表还是分段打表的方法并能独立写出带预计算答案表的提交代码。一文读懂打表是什么朴素打表的定义朴素打表Naive Precomputation的操作流程非常直白在比赛时把所有可能的输入对应的答案都计算出来并保存下来然后在代码里开个数组把答案放进去直接输出即可。也就是说如果题目输入只有一个整数 $n$且 $n$ 的值域很小那么我们可以枚举 $n$ 的所有取值逐一算出答案存进数组ans[]提交的代码里只需要#include bits/stdc.h using namespace std; // 示意假设 n 值域为 [1, 10]答案已预先算好 long long ans[] {0, 1, 5, 14, 30, 55, 91, 140, 204, 285, 385}; int main() { int n; cin n; cout ans[n] \n; return 0; }这里数组ans就是答案表lookup table程序运行时的全部工作只剩一次数组下标访问时间复杂度是 $O(1)$几乎不存在超时风险。朴素打表的适用边界与三大风险dictionary.md明确指出注意这个技巧只适用于输入的值域不大如输入只有一个数而且范围很小的问题否则可能会导致代码过长、MLE、打表需要的时间过长等问题。因此朴素打表有严格的适用前提——输入值域足够小。一旦值域变大会立刻触发三个连锁问题代码过长每个答案都需要一个字面量写进源码。若值域是 $10^9$即便每个答案只占 10 字节生成的源代码也会达到 GB 量级远超绝大多数 OJ 的代码长度限制直接导致提交被拒。MLE内存超限把巨量答案开成数组会撑爆内存。即使侥幸通过编译运行时静态数组的内存占用也会超过题目的内存限制。打表时间过长生成 $10^9$ 个答案本身就是一次 $10^9$ 量级的枚举即使在本机跑也需要很长时间赛时条件下不可接受。正是为了规避这三类风险我们需要对答案表本身进行压缩这就引出了分段打表。分段打表用分块思想压缩答案表前置知识分块思想速览分段打表的前置知识是 分块。分块sqrt decomposition在 OI-wiki 中被定义为一种思想而非具体数据结构分块的基本思想是通过对原数据的适当划分并在划分后的每一个块上预处理部分信息从而较一般的暴力算法取得更优的时间复杂度。分块的时间复杂度主要取决于块长。在经典的分块区间和问题中将长度为 $n$ 的序列按每 $s$ 个元素分成一块查询/修改的最坏复杂度为 $O\left(\frac{n}{s}s\right)$利用均值不等式可知当 $s\sqrt n$ 时取到最优 $O(\sqrt n)$。这一结论在仓库的 分块参考实现 中有直接印证int main() { int n; cin n; len sqrt(n); // 均值不等式可知复杂度最优为根号n for (int i 1; i n; i) { cin a[i]; id[i] (i - 1) / len 1; s[id[i]] a[i]; } // ... }该实现中id[i]表示元素所属块编号、s[i]维护第i个块的区间和查询/修改时对不完整块暴力处理、对完整块直接利用预处理的块信息——这一整块直接取、零块暴力算的处理模式正是分段打表的核心骨架详见 docs/ds/code/decompose/decompose_1.cpp。核心思路块内预计算 查询时分治分段打表把同样的思想应用到答案表上采用分块的思想设置一个合理的步长 $m$这个步长一般视代码长度而定对于第 $i$ 块计算出$$ \sum_{k\frac{n}{m}(i-1)1}^{\frac{ni}{m}} f^2(k) $$的值。然后输出答案时采用分块思想处理即可整块的答案用预处理的值计算非整块的答案暴力计算。这里的关键变化是我们不再为每一个输入存一个答案而是为每一段输入存一个聚合答案。以「对函数值求和」类问题为例设原问题是求 $F(x)\sum_{i1}^{x} f(i)$输入 $x$ 值域很大按步长 $m$ 把值域 $[1,n]$ 切成约 $\frac{n}{m}$ 块第 $i$ 块覆盖 $(\frac{n}{m}(i-1),\frac{ni}{m}]$ 这段区间本地预计算时把每一块内所有函数值的和存进表block[]提交的代码只携带block[]约 $\frac{n}{m}$ 个数查询 $F(x)$ 时完整块直接累加预存的block[i]每块 $O(1)$不完整块即 $x$ 所在的那一段暴力枚举区间内的每个数计算 $f(k)$ 并累加代价为 $O(m)$。最终单次查询的时间复杂度约为 $O\left(m\frac{n}{m}\right)$而代码中携带的答案数据量从 $O(n)$ 压缩到了 $O\left(\frac{n}{m}\right)$完美绕开代码过长与 MLE 两大障碍。最后一个块可能是不完整的当 $n$ 不是 $m$ 的倍数时但这与 分块文档 中最后一个块可以是不完整的这一结论一样并不影响正确性。例题二进制 1 的个数平方和文档给出了一个能完整展现整个思路的例题规定 $f(x)$ 为整数 $x$ 的二进制表示中 $1$ 的个数。输入一个正整数 $n\ (n\leq 10^9)$输出 $\sum_{i1}^n f^2(i)$。为什么朴素打表不可行如果对每一个 $n$ 都直接存答案 $F(n)\sum_{i1}^n f^2(i)$那么表长高达 $10^9$即使每个答案只用一个int也需要约 4 GB 内存必然MLE即便用更紧凑的存储把 $10^9$ 个答案写成源码字面量代码体积也会超过最大代码长度限制导致编译不通过。这正是文档中强调的除了可能会 MLE 外还有可能代码超过最大代码长度限制导致编译不通过。分段打表方案取步长 $m10^6$则整张表只需 $\frac{10^9}{10^6}1000$ 个块。本地预计算时对第 $i$ 块求出$$ \sum_{km(i-1)1}^{mi} f^2(k) $$并存入表提交代码里只有 1000 个long long常量。查询 $F(n)$ 时完整块$k1 \sim \lfloor n/m \rfloor \cdot m$累加预存的块和共约 $\frac{n}{m}$ 次 $O(1)$ 累加非完整块$k\lfloor n/m \rfloor \cdot m 1 \sim n$暴力枚举至多 $m$ 个数逐个用位运算计算二进制 1 的个数再累加平方。单次查询最坏约 $m$ 次popcount计算$10^6$ 量级位运算完全在时限内而预计算那 $O(n\log n)$ 的开销全部发生在本机与提交代码的运行时间无关。复杂度与块长选择分段打表的两个核心指标如下指标朴素打表分段打表代码携带的答案数据量$O(n)$$O\left(\frac{n}{m}\right)$单次查询时间复杂度$O(1)$$O\left(m\frac{n}{m}\right)$不完整块暴力预计算时间$O(n \cdot T_f)$本机执行$O(n \cdot T_f)$本机执行其中 $T_f$ 是单次计算函数值 $f(x)$ 的耗时。与 分块文档 中分块的时间复杂度主要取决于分块的块长一般可以通过均值不等式求出某个问题下的最优块长同理分段打表的理论最优步长也可由均值不等式取 $\frac{n}{m}$ 与 $m$ 的平衡点得到。但文档同时强调——步长 m 一般视代码长度而定$m$ 越大表越短、代码体积越小但查询时暴力部分越慢$m$ 越小查询越快但表越长、代码越长。实际比赛中需要同时权衡 OJ 的代码长度限制、内存限制与时限取一个代码足够短、查询足够快的中间值例如 $10^9$ 值域取 $5\times 10^5 \sim 10^6$。实战从打表代码到提交代码本地预计算示意代码以下给出针对上述例题的分段打表预计算程序示意代码用于说明思路并非仓库自带代码它在本地运行负责生成答案表#include bits/stdc.h using namespace std; const long long N 1000000000LL; // n 的上界 const long long M 1000000LL; // 步长 m可按代码长度限制调整 vectorlong long block; // block[i] 表示第 i 个完整块的函数值之和 int popcount(long long x) { // 计算二进制中 1 的个数 int c 0; while (x) c x 1, x 1; return c; } int main() { long long cur 0; for (long long k 1; k N; k) { int f popcount(k); cur 1LL * f * f; // 累加 f^2(k) if (k % M 0) { // 每攒满一个块记录块和 block.push_back(cur); cerr block[ block.size() - 1 ] cur \n; } } return 0; }运行后将block数组的 1000 个值以常量数组的形式贴进提交代码即可也可以直接用constexpr long long block[] {...}存储见后文进阶用法。提交代码的结构提交到 OJ 的代码结构如下——它只携带答案表与查询逻辑不再包含任何预计算逻辑#include bits/stdc.h using namespace std; const long long M 1000000LL; // 本地预计算得到的块和表示意仅展示前 3 项 const long long block[] {0, 1524412, 7546909, ...}; // 共约 N/M 1000 项 int popcount(long long x) { int c 0; while (x) c x 1, x 1; return c; } long long query(long long n) { long long full n / M; // 完整块的个数 long long ans 0; for (long long i 0; i full; i) ans block[i]; // 完整块直接用预存值 for (long long k full * M 1; k n; k) { // 不完整块暴力 int f popcount(k); ans 1LL * f * f; } return ans; } int main() { long long n; cin n; cout query(n) \n; return 0; }这份提交代码的存储量约 $1000 \times 8\text{ B}8\text{ KB}$ 常量运行时间主要是最后不足 $m$ 个数的暴力段整体非常轻量。什么场景适合分段打表dictionary.md对分段打表的适用场景给出了非常明确的判据一般来说这样的问题对于处理单个函数值 $f(x)$ 很快但是需要大量函数值求和求积或某些可以快速合并的操作枚举会超出时间限制在找不到标准做法的情况下分段打表是一个不错的选择。可以据此提炼出四个同时满足的适用条件单点函数值计算很快$f(x)$ 本身能在很短的时间内如 $O(\log x)$ 或 $O(1)$求出否则不完整块内的暴力段也会超时目标是对大量函数值做可快速合并的操作求和、求积、取最大值等整块信息能够被合并进一个数从而支持块级预计算全量枚举会超时直接枚举全部输入会超出时限否则不需要打表暴力即可找不到或来不及推出标准做法打表本质上是一种以空间/预计算换时间的工程性退路通常是在正解推不出来的情况下使用。从实现角度补一句分段打表之所以可行前提是每个块的和与块内元素之间可以快速互相转化——即块信息可合并。这与 分块文档 中整块直接取、零块暴力算的通用分块框架完全一致。打表的进阶用法与注意事项当指数不是定值时也可以打表dictionary.md给出的第一条注意事项当上题中指数不是定值但是范围较小也可以考虑打表。即原例题中若把 $f^2(i)$ 推广为 $f^a(i)$$a$ 不是固定常数只要指数 $a$ 的取值范围较小仍可以对每个可能的指数分别打表或打一张函数值表后再组合计算不必拘泥于指数固定的情形。判断标准始终是输入/参数的值域是否小到打表可承受。用constexpr把表放进编译期OI-wiki 的 constexpr 详解 指出算法题中可以使用constexpr存储数据规模较小的变量以消除对应的运行时计算开销。尤为常见在「打表」技巧中使用constexpr修饰的数组等容器存储答案。用constexpr修饰答案数组后表的所有值在编译期就已确定运行时无需任何初始化开销如果配合常量下标访问整个查询甚至可能在编译期被直接优化为立即数输出。但该文档同时给出一个重要的反面警告编译器会限制编译时计算的开销如果计算量过大会导致无法通过编译应该考虑使用const。例如constexpr unsigned long long fib(32)这种递归深度过大的编译期计算会触发 evaluation exceeded maximum depth 编译错误见 docs/lang/const.md。因此表很小、值可直接由编译器在编译期算出时用constexpr表很大或由外部预计算脚本生成时用普通全局const数组即可。打表在其他知识模块中的常见用途打表思想在仓库其他文档中还有两类高频用法可作为补充理解素数表等基础表的预处理在 Pollard-Rho 算法 中预先筛出素数表可将试除复杂度从 $O(\sqrt N)$ 降到 $O\left(\frac{\sqrt N}{\ln N}\right)$这是打一张标准答案表的典型应用通过打表猜测结论在 WQS 二分 中可以通过打表、感性理解等方式猜测凸性成立在 公平博弈与 SG 函数 中写一个暴力打表的程序是发现 SG 函数规律、进而归纳证明的关键一步。这说明打表不仅是保底手段也是发现规律、辅助推理的研究工具。经典例题以下两道题来自dictionary.md的例题列表都是练习分段打表的绝佳素材「BZOJ 3798」特殊的质数求区间 $[l,r]$ 内有多少个质数可以分解为两个正整数的平方和。单个数是否为满足条件的质数可以在 $O(\sqrt x)$ 乃至更快的时间内判定但 $l,r$ 区间跨度很大、逐个数枚举会超时因此先把区间按步长分块、预计算每块内满足条件的数的个数查询时整块取预存值、边界块暴力判定即可。「Luogu P1822」魔法指纹这是一道以区间统计为背景的经典打表题题面给出的魔法指纹函数单点计算很快、而需要统计的区间范围很大与分段打表的适用条件高度吻合适合作为读完全文后的第一个练手对象。小结打表是算法竞赛中性价比极高的一项技巧它的完整方法论可以浓缩为一张决策链输入值域小 →朴素打表全部答案直接存数组$O(1)$ 输出值域大、但单点函数值好算且需求可块级合并 →分段打表用分块思想把 $O(n)$ 的答案表压缩为 $O(n/m)$ 的块和表完整块直接取、不完整块暴力算步长 $m$ 在代码长度与查询速度之间权衡当找不到标准做法、枚举会超时、且满足上述条件时分段打表是找不到标准做法的情况下的一个不错的选择原文档原话。分块思想是这一切的地基建议读者先通读 docs/ds/decompose.md 并对照 分块参考实现 理解整块取、零块算的处理模式再回到打表场景中实践。打表不丢人——能把正确性保住、把复杂度压住本身就是一种合格的竞赛工程能力。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI-wiki 竞赛技巧：打表与分段打表全解析
OI-wiki 竞赛技巧打表与分段打表全解析【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki打表Precomputation / Table Lookup是算法竞赛中一种非常实用的退路型技巧当题目数据范围小到可以直接枚举或标准解法难以在赛时推出来时提前把所有答案算好、存进代码里直接输出。本文基于 OI-wiki 的 竞赛技巧·打表 文档完整讲解朴素打表的适用边界、用分块思想实现的分段打表分段打表及其复杂度原理并结合仓库内 分块思想、分块参考实现 与 constexpr 编译期存储 给出可落地的实战方案。读完本文你将掌握判断什么题能打表、该朴素打表还是分段打表的方法并能独立写出带预计算答案表的提交代码。一文读懂打表是什么朴素打表的定义朴素打表Naive Precomputation的操作流程非常直白在比赛时把所有可能的输入对应的答案都计算出来并保存下来然后在代码里开个数组把答案放进去直接输出即可。也就是说如果题目输入只有一个整数 $n$且 $n$ 的值域很小那么我们可以枚举 $n$ 的所有取值逐一算出答案存进数组ans[]提交的代码里只需要#include bits/stdc.h using namespace std; // 示意假设 n 值域为 [1, 10]答案已预先算好 long long ans[] {0, 1, 5, 14, 30, 55, 91, 140, 204, 285, 385}; int main() { int n; cin n; cout ans[n] \n; return 0; }这里数组ans就是答案表lookup table程序运行时的全部工作只剩一次数组下标访问时间复杂度是 $O(1)$几乎不存在超时风险。朴素打表的适用边界与三大风险dictionary.md明确指出注意这个技巧只适用于输入的值域不大如输入只有一个数而且范围很小的问题否则可能会导致代码过长、MLE、打表需要的时间过长等问题。因此朴素打表有严格的适用前提——输入值域足够小。一旦值域变大会立刻触发三个连锁问题代码过长每个答案都需要一个字面量写进源码。若值域是 $10^9$即便每个答案只占 10 字节生成的源代码也会达到 GB 量级远超绝大多数 OJ 的代码长度限制直接导致提交被拒。MLE内存超限把巨量答案开成数组会撑爆内存。即使侥幸通过编译运行时静态数组的内存占用也会超过题目的内存限制。打表时间过长生成 $10^9$ 个答案本身就是一次 $10^9$ 量级的枚举即使在本机跑也需要很长时间赛时条件下不可接受。正是为了规避这三类风险我们需要对答案表本身进行压缩这就引出了分段打表。分段打表用分块思想压缩答案表前置知识分块思想速览分段打表的前置知识是 分块。分块sqrt decomposition在 OI-wiki 中被定义为一种思想而非具体数据结构分块的基本思想是通过对原数据的适当划分并在划分后的每一个块上预处理部分信息从而较一般的暴力算法取得更优的时间复杂度。分块的时间复杂度主要取决于块长。在经典的分块区间和问题中将长度为 $n$ 的序列按每 $s$ 个元素分成一块查询/修改的最坏复杂度为 $O\left(\frac{n}{s}s\right)$利用均值不等式可知当 $s\sqrt n$ 时取到最优 $O(\sqrt n)$。这一结论在仓库的 分块参考实现 中有直接印证int main() { int n; cin n; len sqrt(n); // 均值不等式可知复杂度最优为根号n for (int i 1; i n; i) { cin a[i]; id[i] (i - 1) / len 1; s[id[i]] a[i]; } // ... }该实现中id[i]表示元素所属块编号、s[i]维护第i个块的区间和查询/修改时对不完整块暴力处理、对完整块直接利用预处理的块信息——这一整块直接取、零块暴力算的处理模式正是分段打表的核心骨架详见 docs/ds/code/decompose/decompose_1.cpp。核心思路块内预计算 查询时分治分段打表把同样的思想应用到答案表上采用分块的思想设置一个合理的步长 $m$这个步长一般视代码长度而定对于第 $i$ 块计算出$$ \sum_{k\frac{n}{m}(i-1)1}^{\frac{ni}{m}} f^2(k) $$的值。然后输出答案时采用分块思想处理即可整块的答案用预处理的值计算非整块的答案暴力计算。这里的关键变化是我们不再为每一个输入存一个答案而是为每一段输入存一个聚合答案。以「对函数值求和」类问题为例设原问题是求 $F(x)\sum_{i1}^{x} f(i)$输入 $x$ 值域很大按步长 $m$ 把值域 $[1,n]$ 切成约 $\frac{n}{m}$ 块第 $i$ 块覆盖 $(\frac{n}{m}(i-1),\frac{ni}{m}]$ 这段区间本地预计算时把每一块内所有函数值的和存进表block[]提交的代码只携带block[]约 $\frac{n}{m}$ 个数查询 $F(x)$ 时完整块直接累加预存的block[i]每块 $O(1)$不完整块即 $x$ 所在的那一段暴力枚举区间内的每个数计算 $f(k)$ 并累加代价为 $O(m)$。最终单次查询的时间复杂度约为 $O\left(m\frac{n}{m}\right)$而代码中携带的答案数据量从 $O(n)$ 压缩到了 $O\left(\frac{n}{m}\right)$完美绕开代码过长与 MLE 两大障碍。最后一个块可能是不完整的当 $n$ 不是 $m$ 的倍数时但这与 分块文档 中最后一个块可以是不完整的这一结论一样并不影响正确性。例题二进制 1 的个数平方和文档给出了一个能完整展现整个思路的例题规定 $f(x)$ 为整数 $x$ 的二进制表示中 $1$ 的个数。输入一个正整数 $n\ (n\leq 10^9)$输出 $\sum_{i1}^n f^2(i)$。为什么朴素打表不可行如果对每一个 $n$ 都直接存答案 $F(n)\sum_{i1}^n f^2(i)$那么表长高达 $10^9$即使每个答案只用一个int也需要约 4 GB 内存必然MLE即便用更紧凑的存储把 $10^9$ 个答案写成源码字面量代码体积也会超过最大代码长度限制导致编译不通过。这正是文档中强调的除了可能会 MLE 外还有可能代码超过最大代码长度限制导致编译不通过。分段打表方案取步长 $m10^6$则整张表只需 $\frac{10^9}{10^6}1000$ 个块。本地预计算时对第 $i$ 块求出$$ \sum_{km(i-1)1}^{mi} f^2(k) $$并存入表提交代码里只有 1000 个long long常量。查询 $F(n)$ 时完整块$k1 \sim \lfloor n/m \rfloor \cdot m$累加预存的块和共约 $\frac{n}{m}$ 次 $O(1)$ 累加非完整块$k\lfloor n/m \rfloor \cdot m 1 \sim n$暴力枚举至多 $m$ 个数逐个用位运算计算二进制 1 的个数再累加平方。单次查询最坏约 $m$ 次popcount计算$10^6$ 量级位运算完全在时限内而预计算那 $O(n\log n)$ 的开销全部发生在本机与提交代码的运行时间无关。复杂度与块长选择分段打表的两个核心指标如下指标朴素打表分段打表代码携带的答案数据量$O(n)$$O\left(\frac{n}{m}\right)$单次查询时间复杂度$O(1)$$O\left(m\frac{n}{m}\right)$不完整块暴力预计算时间$O(n \cdot T_f)$本机执行$O(n \cdot T_f)$本机执行其中 $T_f$ 是单次计算函数值 $f(x)$ 的耗时。与 分块文档 中分块的时间复杂度主要取决于分块的块长一般可以通过均值不等式求出某个问题下的最优块长同理分段打表的理论最优步长也可由均值不等式取 $\frac{n}{m}$ 与 $m$ 的平衡点得到。但文档同时强调——步长 m 一般视代码长度而定$m$ 越大表越短、代码体积越小但查询时暴力部分越慢$m$ 越小查询越快但表越长、代码越长。实际比赛中需要同时权衡 OJ 的代码长度限制、内存限制与时限取一个代码足够短、查询足够快的中间值例如 $10^9$ 值域取 $5\times 10^5 \sim 10^6$。实战从打表代码到提交代码本地预计算示意代码以下给出针对上述例题的分段打表预计算程序示意代码用于说明思路并非仓库自带代码它在本地运行负责生成答案表#include bits/stdc.h using namespace std; const long long N 1000000000LL; // n 的上界 const long long M 1000000LL; // 步长 m可按代码长度限制调整 vectorlong long block; // block[i] 表示第 i 个完整块的函数值之和 int popcount(long long x) { // 计算二进制中 1 的个数 int c 0; while (x) c x 1, x 1; return c; } int main() { long long cur 0; for (long long k 1; k N; k) { int f popcount(k); cur 1LL * f * f; // 累加 f^2(k) if (k % M 0) { // 每攒满一个块记录块和 block.push_back(cur); cerr block[ block.size() - 1 ] cur \n; } } return 0; }运行后将block数组的 1000 个值以常量数组的形式贴进提交代码即可也可以直接用constexpr long long block[] {...}存储见后文进阶用法。提交代码的结构提交到 OJ 的代码结构如下——它只携带答案表与查询逻辑不再包含任何预计算逻辑#include bits/stdc.h using namespace std; const long long M 1000000LL; // 本地预计算得到的块和表示意仅展示前 3 项 const long long block[] {0, 1524412, 7546909, ...}; // 共约 N/M 1000 项 int popcount(long long x) { int c 0; while (x) c x 1, x 1; return c; } long long query(long long n) { long long full n / M; // 完整块的个数 long long ans 0; for (long long i 0; i full; i) ans block[i]; // 完整块直接用预存值 for (long long k full * M 1; k n; k) { // 不完整块暴力 int f popcount(k); ans 1LL * f * f; } return ans; } int main() { long long n; cin n; cout query(n) \n; return 0; }这份提交代码的存储量约 $1000 \times 8\text{ B}8\text{ KB}$ 常量运行时间主要是最后不足 $m$ 个数的暴力段整体非常轻量。什么场景适合分段打表dictionary.md对分段打表的适用场景给出了非常明确的判据一般来说这样的问题对于处理单个函数值 $f(x)$ 很快但是需要大量函数值求和求积或某些可以快速合并的操作枚举会超出时间限制在找不到标准做法的情况下分段打表是一个不错的选择。可以据此提炼出四个同时满足的适用条件单点函数值计算很快$f(x)$ 本身能在很短的时间内如 $O(\log x)$ 或 $O(1)$求出否则不完整块内的暴力段也会超时目标是对大量函数值做可快速合并的操作求和、求积、取最大值等整块信息能够被合并进一个数从而支持块级预计算全量枚举会超时直接枚举全部输入会超出时限否则不需要打表暴力即可找不到或来不及推出标准做法打表本质上是一种以空间/预计算换时间的工程性退路通常是在正解推不出来的情况下使用。从实现角度补一句分段打表之所以可行前提是每个块的和与块内元素之间可以快速互相转化——即块信息可合并。这与 分块文档 中整块直接取、零块暴力算的通用分块框架完全一致。打表的进阶用法与注意事项当指数不是定值时也可以打表dictionary.md给出的第一条注意事项当上题中指数不是定值但是范围较小也可以考虑打表。即原例题中若把 $f^2(i)$ 推广为 $f^a(i)$$a$ 不是固定常数只要指数 $a$ 的取值范围较小仍可以对每个可能的指数分别打表或打一张函数值表后再组合计算不必拘泥于指数固定的情形。判断标准始终是输入/参数的值域是否小到打表可承受。用constexpr把表放进编译期OI-wiki 的 constexpr 详解 指出算法题中可以使用constexpr存储数据规模较小的变量以消除对应的运行时计算开销。尤为常见在「打表」技巧中使用constexpr修饰的数组等容器存储答案。用constexpr修饰答案数组后表的所有值在编译期就已确定运行时无需任何初始化开销如果配合常量下标访问整个查询甚至可能在编译期被直接优化为立即数输出。但该文档同时给出一个重要的反面警告编译器会限制编译时计算的开销如果计算量过大会导致无法通过编译应该考虑使用const。例如constexpr unsigned long long fib(32)这种递归深度过大的编译期计算会触发 evaluation exceeded maximum depth 编译错误见 docs/lang/const.md。因此表很小、值可直接由编译器在编译期算出时用constexpr表很大或由外部预计算脚本生成时用普通全局const数组即可。打表在其他知识模块中的常见用途打表思想在仓库其他文档中还有两类高频用法可作为补充理解素数表等基础表的预处理在 Pollard-Rho 算法 中预先筛出素数表可将试除复杂度从 $O(\sqrt N)$ 降到 $O\left(\frac{\sqrt N}{\ln N}\right)$这是打一张标准答案表的典型应用通过打表猜测结论在 WQS 二分 中可以通过打表、感性理解等方式猜测凸性成立在 公平博弈与 SG 函数 中写一个暴力打表的程序是发现 SG 函数规律、进而归纳证明的关键一步。这说明打表不仅是保底手段也是发现规律、辅助推理的研究工具。经典例题以下两道题来自dictionary.md的例题列表都是练习分段打表的绝佳素材「BZOJ 3798」特殊的质数求区间 $[l,r]$ 内有多少个质数可以分解为两个正整数的平方和。单个数是否为满足条件的质数可以在 $O(\sqrt x)$ 乃至更快的时间内判定但 $l,r$ 区间跨度很大、逐个数枚举会超时因此先把区间按步长分块、预计算每块内满足条件的数的个数查询时整块取预存值、边界块暴力判定即可。「Luogu P1822」魔法指纹这是一道以区间统计为背景的经典打表题题面给出的魔法指纹函数单点计算很快、而需要统计的区间范围很大与分段打表的适用条件高度吻合适合作为读完全文后的第一个练手对象。小结打表是算法竞赛中性价比极高的一项技巧它的完整方法论可以浓缩为一张决策链输入值域小 →朴素打表全部答案直接存数组$O(1)$ 输出值域大、但单点函数值好算且需求可块级合并 →分段打表用分块思想把 $O(n)$ 的答案表压缩为 $O(n/m)$ 的块和表完整块直接取、不完整块暴力算步长 $m$ 在代码长度与查询速度之间权衡当找不到标准做法、枚举会超时、且满足上述条件时分段打表是找不到标准做法的情况下的一个不错的选择原文档原话。分块思想是这一切的地基建议读者先通读 docs/ds/decompose.md 并对照 分块参考实现 理解整块取、零块算的处理模式再回到打表场景中实践。打表不丢人——能把正确性保住、把复杂度压住本身就是一种合格的竞赛工程能力。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考