分段打表
在学习之前请先学习分块。
打表大家都知道，就是在比赛时把答案都输出出来，然后开个数组，把答案直接存入数组里。于是你的代码时间复杂度就是 的了。
但是需要注意这个技巧只适用于类似输出某函数值类的问题。比如规定 为整数 的二进制表示中 的个数。输入一个正整数 ，输出 。这样的话 不大时，采用打表的方法可以做到 的复杂度。
注意到这个问题其实十分的简单，采用一般做法也可以做到 的复杂度，但是 ？
还有一些时候，打出来的表十分大，如果对于每一个 ，都输出 的话，那么 MLE 之外，还有可能代码超过最大代码长度限制，导致编译前不通过（代码可能直接被 pass）。
我们考虑优化这个答案表，借用分块思想，我们设置一个合理的步长 （这个步长一般视代码长度而定），对于第 块，输出：
的值。
然后输出答案时借用分块思想处理即可。
一般来说，这样的问题对于处理单个函数值 很快，但是需要大量函数值求和（求积或某些可以快速合并的操作），枚举会超出时间限制，在找不到标准做法的情况下，分段打表是一个不错的选择。
注意事项¶
- 当上题中指数不是定值，但是范围较小，也可以考虑打表；
- 上题是本人为了介绍分段打表口胡出来的，如已有此题纯属巧合。
例题¶
「BZOJ 3798」特殊的质数：权限题……不过可以在各大 BZ 离线题库中看到。
题意简述：求 区间内有多少个质数可以分解为两个正整数的平方和。——via PoPoQQQ
「Luogu P1822」魔法指纹：其实是一道暴搜，不过可以练练分段打表。
明明是我先写的分段打表为什么你们这么熟练 QAQ，可以对比下我的题解的发布时间和 Luogu 中的。
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用