基本技巧——分段打表学习笔记

分段打表，也叫间隔打表。

打表

在比赛时把所有可能的输入对应的答案都计算出来并保存下来，然后在代码里开个数组把答案放里面，直接输出即可。

这个技巧只适用于输入的值域不大（如，输入只有一个数，而且范围很小）的问题，否则可能会导致代码过长、MLE、打表需要的时间过长等问题。

将输入分为若干的块，计算整块的答案，然后利用整块的答案递推得到所有答案。

但是分段打表对题目也有一些要求：

答案可递推
也就是通过 \(f(k)\) 可以递推出 \(f(k+1)\)，直到 \(f(n)\)，且递推复杂度可以接受。
差分思想
需要求的东西，一个数 \(x\) 还好说，一个区间 \([l,r]\) 的问题，就需要差分一下，即 \(f(l,r)=f'(r)-f'(l-1)\)。
打表的间隔
越短速度越快，但是代码体积越大，因此需要合适的选择。