

分段打表

在学习之前请先学习 分块 。

打表大家都知道，就是在比赛时把答案都输出出来，然后开个数组，把答案直接存入数组里。于是你的代码时间复杂度就是 $O(1)$ 的了。

但是需要注意这个技巧只适用于类似输出某函数值类的问题。比如规定 $f(x)$ 为整数 $x$ 的二进制表示中 $1$ 的个数。输入一个正整数 $n$ ，输出 $\sum_{i=1}^nf^2(i)$ 。这样的话 $n$ 不大时，采用打表的方法可以做到 $O(1)$ 的复杂度。

注意到这个问题其实十分的简单，采用一般做法也可以做到 $O(n\log n)$ 的复杂度，但是 $n=10^9$ ？

还有一些时候，打出来的表十分大，如果对于每一个 $n$ ，都输出 $f(n)$ 的话，那么 MLE 之外，还有可能代码超过最大代码长度限制，导致编译前不通过（代码可能直接被 pass）。

我们考虑优化这个答案表，借用分块思想，我们设置一个合理的步长 $m$ （这个步长一般视代码长度而定），对于第 $i$ 块，输出：

$$\Large \sum_{k=\frac{n}{m}(i-1)+1}^{\frac{ni}{m}} f^2(k)$$

的值。

然后输出答案时借用分块思想处理即可。

一般来说，这样的问题对于处理单个函数值 $f(x)$ 很快，但是需要大量函数值求和（求积或某些可以快速合并的操作），枚举会超出时间限制，在找不到标准做法的情况下，分段打表是一个不错的选择。

注意事项

1. 当上题中指数不是定值，但是范围较小，也可以考虑打表；
2. 上题是本人为了介绍分段打表口胡出来的，如已有此题纯属巧合。

例题

「BZOJ 3798」特殊的质数 ：权限题……不过可以在各大 BZ 离线题库中看到。

题意简述 ：求 $[l,r]$ 区间内有多少个质数可以分解为两个正整数的平方和。——via PoPoQQQ

「Luogu P1822」魔法指纹 ：其实是一道暴搜，不过可以练练分段打表。

明明是我先写的分段打表为什么你们这么熟练 QAQ，可以对比下 我的题解 的发布时间和 Luogu 中的。

---

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论