分段打表
前置知識：分塊。
樸素的打表，指的是在比賽時把所有可能的輸入對應的答案都計算出來並保存下來，然後在代碼裏開個數組把答案放裏面，直接輸出即可。
注意這個技巧只適用於輸入的值域不大（如，輸入只有一個數，而且範圍很小）的問題，否則可能會導致代碼過長、MLE、打表需要的時間過長等問題。
例題
規定 \(f(x)\) 為整數 \(x\) 的二進制表示中 \(1\) 的個數。輸入一個正整數 \(n\)(\(n\leq 10^9\))，輸出 \(\sum_{i=1}^n f^2(i)\)。
如果對於每一個 \(n\)，都輸出 \(f(n)\) 的話，除了可能會 MLE 外，還有可能代碼超過最大代碼長度限制，導致編譯不通過。
我們考慮優化這個答案表。採用 分塊 的思想，我們設置一個合理的步長 \(m\)（這個步長一般視代碼長度而定），對於第 \(i\) 塊，計算出：
\[
\sum_{k=\frac{n}{m}(i-1)+1}^{\frac{ni}{m}} f^2(k)
\]
的值。
然後輸出答案時採用分塊思想處理即可。即，整塊的答案用預處理的值計算，非整塊的答案暴力計算。
一般來説，這樣的問題對於處理單個函數值 \(f(x)\) 很快，但是需要大量函數值求和（求積或某些可以快速合併的操作），枚舉會超出時間限制，在找不到標準做法的情況下，分段打表是一個不錯的選擇。
注意事項
當上題中指數不是定值，但是範圍較小，也可以考慮打表。
例題
「BZOJ 3798」特殊的質數：求 \([l,r]\) 區間內有多少個質數可以分解為兩個正整數的平方和。
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用