整数分块

什么是整数分块

整数分块（Integer Chunking / Block Decomposition）是一种数论技巧，用于将连续区间分割成若干块，使得在求和、计数等场景下降低计算复杂度。

常见形式：将 $\lfloor n / i \rfloor$ 相同的 $i$ 合并成块，时间复杂度从 $O(n)$ 优化到 $O(\sqrt{n})$ 。

对于任意正整数 $n$ ，序列 $\{\lfloor n / i \rfloor \mid i = 1, 2, \dots, n\}$ 中，相同值出现的 $i$ 是一个连续区间。

设 $v = \lfloor n / i \rfloor$ ，则该值不变的右端点为：

r = \left\lfloor \frac{n}{v} \right\rfloor

因此 $[l, r]$ 区间内的所有 $i$ 都满足 $\lfloor n / i \rfloor = v$ ，可以一次性处理。

求 $\displaystyle \sum_{i=1}^{n} \left\lfloor \frac{n}{i} \right\rfloor$
求解 $\displaystyle \sum_{k=1}^{n} \left\lfloor \frac{n}{k} \right\rfloor$ （数论分块求和）
数论分块优化 DP
区间查询分块

i = 1
while i <= n:
    val = n // i
    next_i = n // val + 1   # r = floor(n / val)
    # 处理 [i, next_i - 1] 区间，值均为 val
    i = next_i

循环次数为 $O(\sqrt{n})$ 级别。