第六章：二分与倍增 · SpringWait Blog

当候选答案能按顺序排列，且一次判断可以排除连续的一半候选时，就可以使用二分。本章先从有序数组查找建立区间不变量，再把查找对象换成答案；最后用倍增预存较长的连续跳跃，减少重复移动。

阅读前需要掌握有序数组、循环和整数范围。倍增使用固定后继关系，步数的二进制拆分在本节说明。

1. 查找指定值

例题：查找。

简易题面：给定单调不减序列和若干询问，输出每个询问值第一次出现的下标，不存在则输出 $-1$ 。

数据范围： $1\le n\le10^6$ ， $1\le m\le10^5$ ； $0\le a_i,q_i\le10^9$ 。

顺序查找每次最多访问全部元素。有序数组允许从中点比较：若中点偏小，左半不可能包含目标；若偏大，右半不可能包含目标。以下先展示返回任意匹配位置的基础写法，再改成例题要求的首次出现位置。全局数组 (a[1]) 至 (a[n]) 已非降序排列，(x) 为当前询问值，(ans=-1) 表示尚未找到。

int l = 1, r = n, ans = -1;
while (l <= r)
{
    int mid = l + (r - l) / 2;
    if (a[mid] == x)
    {
        ans = mid;
        break;
    }
    if (a[mid] < x)
    {
        l = mid + 1;
    }
    else
    {
        r = mid - 1;
    }
}

前提是数组已经有序。使用 (l+(r-l)/2) 可以避免 (l+r) 溢出。

循环中的 ([l,r]) 表示尚未被排除的候选位置。若中点太小，有序性保证 ([l,mid]) 全部太小；若中点太大，([mid,r]) 全部太大。把中点一并排除，区间才能严格缩短。

可以把候选区间想成一排按数值排好序、尚未划掉的卡片。检查中间一张后，划掉的是一整段，而不是只划掉这一张。例如在 $[1,3,5,7,9,11,13,15]$ 中查找 $13$ ：

轮次	检查前的下标范围	中点与比较	排除的位置	剩余位置
$1$	$[1,8]$	$mid=4$ ， $a[4]=7<13$	$[1,4]$ ：值都不超过 $7$	$[5,8]$
$2$	$[5,8]$	$mid=6$ ， $a[6]=11<13$	$[5,6]$ ：值都不超过 $11$	$[7,8]$
$3$	$[7,8]$	$mid=7$ ， $a[7]=13$	不再排除，直接返回	答案下标为 $7$

灰色卡片表示已经排除的位置，蓝色范围表示待查区间。每次未找到目标时，候选数至多减为原来的一半，因此最多进行 $O(\log n)$ 轮检查。

这个片段遇到相等值就结束，所以有重复元素时不保证返回第一次出现的位置。例题查找要求首次出现，应继续寻找左边界。若根本不存在，循环结束后仍为 (ans=-1)，不要把最终中点当成答案。

当边界允许跨越很大的正负范围时，(r-l) 本身也可能超出 ( exttt{int})，仍需要让边界变量使用足够宽的类型；中点写法不能替代范围分析。

2. 查找第一个满足条件的位置

假设条件随位置变化为：

false false false true true true

int l = 1, r = n, ans = n + 1;
while (l <= r)
{
    int mid = l + (r - l) / 2;
    if (check(mid))
    {
        ans = mid;
        r = mid - 1;
    }
    else
    {
        l = mid + 1;
    }
}

找到可行位置后继续向左，寻找第一个。对于首次出现问题，令 (check(mid)) 等价于 (a[mid]\ge x)；搜索结束后，还需检查 (ans\le n) 且 (a[ans]=x)，否则应输出无解。每次查询使用新的 (l,r,ans)，时间为 $O(\log n)$ 。

查找最后一个满足条件的位置时，方向相反。

把“第一个真”看成一个尚待定位的分界线。检查到真时，中点先作为备选答案保存，之后只在左半继续找更早的真；检查到假时，中点及其左侧都可以排除。结束时，(ans) 要么是最早的真，要么保留哨兵 (n+1) 表示一个都没有。

例如真假序列为“假、假、真、真、真”，初始 $[1,5]$ ：检查 3 为真，记住 3，改查 $[1,2]$ ；再检查 1、2 均为假，最终答案仍是 3。候选位置被排除后，已记录的答案不会丢失。

重复值能展示“找到一个”与“找到第一个”的区别。在 $[1,2,2,2,5]$ 中查询 $2$ ，第一次检查下标 $3$ 就已经相等；但它左侧还有一个 $2$ ，所以不能立即结束。把条件写成 $a[mid]\ge 2$ ，得到的真假排列为“假、真、真、真、真”：

轮次	检查前的范围	判断结果	保存的答案	下一轮范围
$1$	$[1,5]$	$mid=3$ ，条件为真	$ans=3$	$[1,2]$
$2$	$[1,2]$	$mid=1$ ，条件为假	$ans=3$	$[2,2]$
$3$	$[2,2]$	$mid=2$ ，条件为真	$ans=2$	$[2,1]$ ，区间为空

第一次保存答案后，下标 $3$ 已在待查范围之外，但答案标记仍然保留。这里 $r=mid-1$ 的前提是已经执行了 $ans=mid$ ；若只排除中点而不保存，就可能丢失答案。

“最后一个真”常对应“真……真、假……假”：真时保存并向右找，假时向左找。应先画出真假排列，再决定移动方向，而不是只改一个比较符号。

3. STL 边界函数

以下仍查询同一个有序全局数组。两个返回迭代器减去首地址后得到一号下标；(n+1) 是尾后位置，只能比较，不能作为有效元素读取。

int p1 = lower_bound(a + 1, a + n + 1, x) - a;
int p2 = upper_bound(a + 1, a + n + 1, x) - a;

$\texttt{lower\_bound}$ ：第一个大于等于 (x)；
$\texttt{upper\_bound}$ ：第一个大于 (x)；
(p2-p1)：(x) 的出现次数。

返回位置可能是 (n+1)，使用前必须判断。

数组 $[1,2,2,2,5]$ 中查询 $2$ ，(p1=2)、(p2=5)，出现次数为 $3$ 。查询不存在的 $3$ ，两个位置都为 $5$ ，差为零；查询 $6$ ，两个位置都为 (n+1)。

目标同为 $2$ 时，三个值为 $2$ 的位置在 $a[mid]\ge 2$ 下都为真，在 $a[mid]>2$ 下都为假。因此两个分界点分别落在下标 $2$ 和 $5$ ，相等元素恰好占据半开区间 $[2,5)$ 。这两幅动图使用手写二分展示边界的含义，不表示 STL 函数必须按相同顺序访问元素。

要判断值是否存在，应先检查 $p1\le n$ ，再检查 (a[p1]=x)。 $\texttt{lower\_bound}$ 返回的是“不小于目标”的边界，目标缺失时也会正常返回一个位置。调用前必须保证数组按相容的比较规则有序。

4. 二分答案

例题：数列分段 Section II。

简易题面：将长度为 $n$ 的非负整数序列分成恰好 $m$ 个非空连续段，使各段元素和的最大值最小。输出这个最小值。

数据范围： $1\le m\le n\le10^5$ ； $0\le a_i<10^8$ ，答案不超过 $10^9$ 。

直接选择 $m-1$ 个切分位置，会产生大量方案。逐个构造最优划分较难，但给定一个段和上限后，只需判断能否在规定段数内装下全部元素。于是可以把求最优值改成判定，再寻找最小可行上限。

把非负序列切成 (m) 个非空连续段，最小化最大段和。最小候选至少是单个元素最大值，最大候选可以取全体总和；上界的类型要容纳总和，不能只看最后输出答案的范围。

给定段和上限 (x)，从左到右尽量把元素放入当前段，只有再放一个就超限时才开新段。任何合法划分的第一段都不能越过这个贪心第一段的终点；按相同论证逐段比较，贪心能用最少的段数覆盖序列。

例如 $[7,2,5,10,8]$ 切两段：上限 $17$ 时，贪心得到 $[7,2,5]$ 、 $[10]$ 、 $[8]$ 三段，不可行；上限 $18$ 时得到 $[7,2,5]$ 、 $[10,8]$ 两段，可行。上限增加只会放宽限制，因此可以找第一个可行值。

这个模型可以想成沿着传送带装箱：元素必须按原顺序装入，每箱容量都是待检查的上限 $x$ ，当前箱再放一个就超限时才换箱。容量增大后，原来能装下的方案仍然能装下，因此可行性只会从假变真。

上方数轴表示候选上限 $10$ 至 $32$ ，下方按顺序放入 $[7,2,5,10,8]$ 。每次取中点后，重新分段，再用所需段数判断上限是否可行。搜索的是容量，不是元素下标。

判定只需检查段数不超过 (m)：元素非负，拆开任意已有段不会增大段和，而且 $m\le n$ 时总能继续拆到恰好 (m) 个非空段。若允许负数，贪心和这个拆分论证都需要重新检查。每次 (check) 都从空段状态开始，不能继承上次候选的计数。

以下全局 $\texttt{int }a[100010],n,m$ 保存输入。元素和可能接近 $10^{13}$ ，因此二分边界、候选值及段内累计和都使用 $\texttt{long long}$ ，即使题面保证最终答案不超过 $10^9$ 。

bool check(long long x)
{
    int cnt = 1;
    long long sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] > x)
        {
            return false;
        }
        if (sum + a[i] > x)
        {
            ++cnt;
            sum = 0;
        }
        sum += a[i];
    }
    return cnt <= m;
}

取 (l) 为最大元素、(r) 为元素总和，便得到包含答案且右端可行的闭区间。下面每轮都保留最小可行值所在的一侧，结束时两端相等。

while (l < r)
{
    long long mid = l + (r - l) / 2;
    if (check(mid))
    {
        r = mid;
    }
    else
    {
        l = mid + 1;
    }
}

当所有元素都为零时，初始 (l=r=0)，无需进入循环，答案就是零。总时间为 $O(n\log(V+1))$ ，其中 $V$ 是搜索范围宽度；输入数组占 $O(n)$ 空间。

对上面的五个数，要求恰好分成两段时，完整的区间变化如下：

检查前的候选上限范围	试用上限	贪心分段	判定结果	更新后的范围
$[10,32]$	$21$	$[7,2,5]$ 、 $[10,8]$	两段，可行	$[10,21]$
$[10,21]$	$15$	$[7,2,5]$ 、 $[10]$ 、 $[8]$	三段，不可行	$[16,21]$
$[16,21]$	$18$	$[7,2,5]$ 、 $[10,8]$	两段，可行	$[16,18]$
$[16,18]$	$17$	$[7,2,5]$ 、 $[10]$ 、 $[8]$	三段，不可行	$[18,18]$

这里判定为真时使用 $r=mid$ ，与前面的 $r=mid-1$ 并不矛盾：前一种写法把中点存入 $ans$ 后继续搜索，本节写法则让答案始终留在 $[l,r]$ 内，没有另存答案。若把本节的更新直接改成 $r=mid-1$ ，第三轮就会丢掉正确答案 $18$ 。

若要求的段数改为 $1$ 或 $5$ ：只有一段时，答案为总和 $32$ ；每个元素单独一段时，答案为最大元素 $10$ 。这两个边界例子也说明了初始范围的两个端点分别来自哪里。

5. 实数二分

简单问题：给定 $0\le n\le10^{12}$ ，求非负平方根，绝对误差不超过 $10^{-6}$ 。

按很小的步长枚举答案，会使次数随精度要求急剧增加。非负数平方随数值增大而增大，因此可以比较中点的平方与 $n$ ，每次排除一半范围。答案位于 $[0,\max(1,n)]$ ，以下 (l,r,n) 均为 $\texttt{double}$ ，并已按这个范围初始化。

for (int t = 1; t <= 100; ++t)
{
    double mid = (l + r) / 2;
    if (mid * mid >= n)
    {
        r = mid;
    }
    else
    {
        l = mid;
    }
}

理想实数运算中，迭代 $t$ 次后区间宽度缩小为原来的 $2^{-t}$ 。本例迭代次数足够，答案也不超过 $10^6$ ， $\texttt{double}$ 能满足所需绝对精度。输出仍要保留足够小数位。实数更新不使用整数二分中的加一、减一；固定次数也能避免端点因浮点舍入不再变化时陷入死循环。

连续函数求根还有另一种二分依据：两端异号时，保留仍然异号的一半。它依赖连续性，不要求整个函数单调；但多根区间只能保证夹住某个根。三次方程等问题必须先分析根的范围与分离条件，不能直接套一个全局单调判定。

6. 倍增

简单问题：远程跳转。

简易题面：有 (n) 个传送点，编号为 $1$ 到 (n)。从传送点 (i) 进行一次传送后，会到达 (nxt_i)。

给定 (q) 次询问。每次询问给出起点 (x) 和非负整数 (k)，请输出从 (x) 出发恰好传送 (k) 次后所在的传送点。

数据范围： $1\le n,q\le2\times10^5$ ； $1\le nxt_i,x\le n$ ； $0\le k\le10^{18}$ 。

逐次模拟每条询问，步数可能达到十亿以上。一步规则固定时，可以预先保存大步跳转，查询时再拼接。程序用 (nxt[i][k]) 保存从位置 (i) 连续走 $2^k$ 步后的位置。连续两段 $2^{k-1}$ 步正好拼成一段 $2^k$ 步，因此可以逐层建表。以下全局 $\texttt{int }nxt[200010][60]$ 保存跳转表，约需 $48$ MB；第一层先读入每个位置的一步后继。

for (int k = 1; k < 60; ++k)
{
    for (int i = 1; i <= n; ++i)
    {
        nxt[i][k] = nxt[nxt[i][k - 1]][k - 1];
    }
}

查询时 (s) 为非负 $\texttt{long long}$ ，且 $s\le10^{18}$ 时预留 $60$ 层即可。(x) 初始为查询起点。每轮用整除 $2$ 和取余 $2$ 提取二进制位：余数为一，就走当前层对应的步数。

for (int k = 0; s > 0; ++k, s /= 2)
{
    if (s % 2 == 1)
    {
        x = nxt[x][k];
    }
}

零步查询直接保留起点，不进入循环。

把走 $13$ 步写成 $8+4+1$ 步，只需完成三次已经预处理好的跳转。(nxt[i][k]) 的计算先走前半段 $2^{k-1}$ 步，再从中途位置继续走同样多的步，因此右侧两个表项都来自较低层。预处理必须先枚举层数，再枚举全部位置。

若最大步数为 (K)，表的时间、空间均为 $O(n \log K)$ ，单次查询为 $O(\log K)$ ；层数取决于步数，而不只是位置个数。 $K\le 10^{18}$ 时需要覆盖第 $0$ 至 $59$ 位，步数使用 $\texttt{long long}$ 。若允许走到不存在的位置，可用 $0$ 作哨兵，并令它在所有层仍跳到 $0$ 。

7. 二分综合模型

7.1 二分操作前缀

例题：NOIP 2012 提高组·借教室。

简易题面：按顺序处理 $m$ 次教室申请，每次在闭区间 $[s_i,t_i]$ 的每天占用 $d_i$ 间。给出每天容量，求第一个无法满足的申请；全部成功则输出 $0$ 。

数据范围： $1\le n,m\le10^6$ ， $0\le r_i,d_i\le10^9$ ， $1\le s_i\le t_i\le n$ 。

若执行前 (k) 个操作后的状态可以快速检查，而且一旦失败，执行更多操作也一定失败，就可以二分第一个失败的操作。

前 (k) 次资源申请可以用差分批量累计，再检查任一天是否超额。申请量非负，因此一旦前 (k) 次已经失败，增加后续申请不可能重新成功，失败条件具有单调性。

每次检查都要清空本次累计数组并只加入前 (k) 次申请。二分尝试的 (k) 不按大小顺序出现，不能默认下一次检查只是给上一次状态追加操作。还应先区分“全部成功”和“存在首次失败”两种输出。

7.2 隐式序列第 $k$ 小

简单问题：乘法表第 K 小。

简易题面：有一个 $n$ 行 $m$ 列的乘法表，第 $i$ 行第 $j$ 列的数为 $i\times j$ 。

把表中的 $n\times m$ 个数按非递减顺序排列，相同的数按出现次数重复保留。求排列后的第 $k$ 个数。

数据范围： $1\le n,m\le 5\times 10^5$ ； $1\le k\le n\times m$ 。

有些有序序列太大，不能完整生成。可以二分候选值 (x)，计算“小于等于 (x) 的元素个数”，再寻找第一个计数达到 (k) 的值。

乘法表第 (i) 行为 (i,2i,\ldots,mi)，其中不超过 (x) 的个数是 $\min(m,\lfloor x/i\rfloor)$ 。对全部行求和，就能知道整个表中不超过 (x) 的元素数，无须生成 (nm) 个元素。

重复值按出现次数计数。寻找第一个“计数至少为 (k)”的 (x)，才能正确处理多个位置拥有同一个值的情况；不能要求计数恰好等于 (k)，因为计数可能一次跳过 (k)。

7.3 平均值参数化

简单问题：最大平均数。

简易题面：给定一个长度为 $n$ 的非负整数序列 $a_1,a_2,\ldots,a_n$ 。请选择一个长度不少于 $m$ 的连续子段，使这个子段的平均数尽可能大。

输出最大平均数乘以 $1000$ 后向下取整的结果。

数据范围： $1\le m\le n\le 10^5$ ； $0\le a_i\le 2000$ 。

判断某段平均值是否至少为 (x) 时，可以把每个数改成 (a[i]-x)，问题转化为是否存在和非负的合法区间。

要求区间长度至少为 (L) 时，设变换后的前缀和为 (s[i])。以 (r) 为右端的区间平均值至少为 (x)，等价于存在 $j\le r-L$ 使 (s[r]-s[j]\ge0)。

因此枚举 (r) 时，维护所有已经允许的前缀位置 $0$ 至 $r-L$ 中的最小值。每轮先把新允许的 (s[r-L]) 加入候选，再检查差是否非负。只维护最近 (L) 项的和，会漏掉长度超过 (L) 的更优区间；把当前前缀也放进去，又可能错误使用空区间。

8. 作业

巩固练习

提高训练

数列分段 Section II