Segmented Precomputation
Naive precomputation (also known as "table-driven" or "lookup table" approach) refers to calculating and storing the answers for all possible inputs during the contest, then placing these answers into an array in the code and outputting them directly.
Note that this technique is only suitable for problems where the input value range is small (e.g., the input is a single number with a small range). Otherwise, it may lead to excessively long code, MLE (Memory Limit Exceeded), or impractically long precomputation time.
Example Problem
Define \(f(x)\) as the number of \(1\)s in the binary representation of integer \(x\). Given a positive integer \(n\) (\(n\leq 10^9\)), output \(\sum_{i=1}^n f^2(i)\).
If we output \(f(n)\) for every \(n\), besides possibly causing MLE, the code might also exceed the maximum code length limit, resulting in a compilation failure.
We consider optimizing this answer table. Using the idea of block decomposition, we set a reasonable step size \(m\) (this step size generally depends on the code length). For the \(i\)-th block, we compute:
Then, when outputting the answer, we process it using the block decomposition idea. That is, the answer for complete blocks is computed using the preprocessed values, while the answer for incomplete blocks is computed by brute force.
Generally, such problems involve computing a single function value \(f(x)\) quickly, but require summing (or multiplying, or performing some other quickly mergeable operation) a large number of function values. Enumeration would exceed the time limit. When a standard solution is not apparent, segmented precomputation (block-based table) is a good alternative.
Note
When the exponent in the above problem is not constant but has a small range, precomputation can also be considered.
Example Problems
「BZOJ 3798」Special Prime Numbers: Count how many prime numbers in the interval \([l,r]\) can be expressed as the sum of squares of two positive integers.
「Luogu P1822」Magic Fingerprint
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用