第 118A 章　整体二分¶

前置：分治的三步框架、二分、树状数组

整体二分把 \(q\) 个各自独立的二分按层同步推进：所有询问共享同一次「把元素塞进数据结构」的代价，于是 \(q\) 次 \(O(\log V \cdot \text{单次判定})\) 摊成 \(O((n+q)\log V\log n)\)。递归对象是（值域区间, 元素集合, 询问集合）三元组。

前提有三条：多个询问、判定单调、不强制在线。少一条就用不了——它只是把多个二分批处理，不能让不能二分的东西变得能二分。

分「时间/下标」的那一支是 CDQ 分治；通用框架在分治的三步框架。

1　整体二分¶

问题背景¶

单个询问「区间 \([l,r]\) 的第 \(k\) 小」怎么做？

二分答案 v：统计 [l,r] 中 <= v 的元素个数 c
   c >= k  ->  答案 <= v，往左半值域找
   c <  k  ->  答案 >  v，往右半值域找（并把 k 减去 c）

每次判定需要「区间内 \(\le v\) 的个数」，用树状数组要 \(O(\log n)\)，所以单个询问是 \(O(\log V\log n)\)，\(q\) 个询问是 \(O(q\log V\log n)\)。

问题出在哪：每个询问独立二分，每次判定都要重新往树状数组里塞元素再撤掉，这部分工作被重复了 \(q\) 遍。

核心思想：把 \(q\) 个二分「同时」做¶

整体二分（parallel binary search）= 把所有询问的二分过程按层同步推进。在值域的第 \(d\) 层，所有还在这一层的询问共享同一次「把元素塞进数据结构」的操作。

先跨过一层观念转换：询问也是被分治的数据。 平时写二分，被分的是「值域」，询问只是站在外面下达指令的一方。整体二分把询问降格成和数组元素同等地位的对象：每一层递归都拿着两袋东西——一袋元素、一袋询问——同时切成两半往下传。元素按「值 \(\le v_m\) 还是 \(> v_m\)」分，询问按「答案在左半值域还是右半」分。 递归树的每个节点因此都是一个「小规模的同类问题」，这正是分治能成立的原因，也是理解整体二分唯一的门槛。

CDQ 的转换更彻底：修改和询问被混进同一条按时间排的序列，然后按下标对半砍。看懂这一步，后面的代码都只是归并而已。

	单独二分	整体二分
递归的对象	一个询问	（值域区间, 元素集合, 询问集合）三元组
层数	\(\log V\)	\(\log V\)
每层的数据结构操作	\(q \times\)（塞 + 撤）	\(n\) 次塞 + \(n\) 次撤（整层共享）
总复杂度	\(O(q\log V\log n)\)	\(O((n+q)\log V\log n)\)

当 \(q \gg 1\) 时整体二分把「\(q\) 倍的塞元素代价」压成了「1 倍」。

算法¶

solve(值域区间 [vl, vr], 元素集合 E, 询问集合 Q):
    if Q 为空: return
    if vl == vr: 所有 Q 中的询问答案都是 vl，return
    vm = (vl + vr) // 2
    把 E 中值 <= vm 的元素塞进树状数组
    for 每个询问 q in Q:
        c = 树状数组查 q 的区间和            ← 「区间内值 <= vm 的个数」
        if c >= q.k:  q 归入左半 QL
        else:         q.k -= c，归入右半 QR   ← ★ k 要减掉
    把刚塞进去的元素全部撤掉                  ← ★ 必须撤，否则污染兄弟分支
    solve([vl, vm],   E 中值 <= vm 的部分, QL)
    solve([vm+1, vr], E 中值 >  vm 的部分, QR)

两个必须记牢的细节：

细节	为什么
归入右半时 `k -= c`	右半的询问已经确定「左半贡献了 \(c\) 个」，剩下要找的是第 \(k-c\) 小
每层结束必须撤销树状数组	递归到兄弟分支时数据结构必须是干净的。忘了撤是整体二分第一大 bug

模板（迭代版，静态区间第 \(k\) 小）¶

数组静态时，「值 \(\le v_m\) 的元素」在「按值排好序的元素列表」里恰好是一段前缀，于是元素集合可以用下标区间 [ilo, ihi] 表示，不需要真的拆列表。

# [片段]
def kth_offline(a, queries):
    """整体二分求**静态**区间第 k 小。

    a       —— 0-indexed 数组
    queries —— [(l, r, k)]，0-indexed 闭区间，k 从 1 开始；★ 会被就地修改（k 递减）
    返回每个询问的答案。

    复杂度 O((n + q) log V log n)。
    ★ 用显式栈而不是递归：层数只有 log V，递归也安全，但迭代少一层函数调用开销。
    """
    n = len(a)
    q = len(queries)
    vals = sorted(set(a))                    # 离散化后的值域
    ans = [0] * q
    bit = [0] * (n + 1)                      # 树状数组：下标 i 处放 1 表示「该位置的值已入库」

    def add(i, v):                           # 下标 i（0-indexed）处 += v
        i += 1                               # 树状数组从 1 计数，0 号位是 lowbit 的死循环点
        while i <= n:
            bit[i] += v
            i += i & -i                      # 逐级上传给管辖自己的父格

    def pre(i):                              # 下标 [0, i] 的和
        i += 1
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i                      # 减 lowbit 逐段回退，最多 log n 步
        return s

    items = sorted(range(n), key=lambda i: a[i])   # 按值排序的下标 —— 全局只排一次
    # 栈里的五元组 = (值域左端, 值域右端, 元素段左端, 元素段右端, 询问编号表)
    stack = [(0, len(vals) - 1, 0, n - 1, list(range(q)))]
    while stack:
        vl, vr, ilo, ihi, qs = stack.pop()
        if not qs:
            continue                         # 没有询问落到这个分支，整棵子树都不用展开
        if vl == vr:                         # 值域收缩到一个点 -> 定答案
            v = vals[vl]
            for j in qs:
                ans[j] = v
            continue
        vm = (vl + vr) // 2
        # ---- 把值 <= vals[vm] 的元素塞进树状数组（它们在 items 里是一段前缀）----
        added = []
        p = ilo
        while p <= ihi and a[items[p]] <= vals[vm]:
            add(items[p], 1)                 # 按「原下标」入库，这样才能按区间查
            added.append(items[p])
            p += 1                           # 循环结束时 p 是左右两段元素的分界
        # ---- 分流询问 ----
        left = []
        right = []
        for j in qs:
            l, r, k = queries[j]
            c = pre(r) - (pre(l - 1) if l > 0 else 0)   # [l, r] 里值 <= vals[vm] 的个数
            if c >= k:                       # 小值够多，第 k 小就藏在左半值域
                left.append(j)
            else:
                queries[j] = (l, r, k - c)   # ★ k 要减掉左半的贡献
                right.append(j)              # 右半只需再找第 k-c 小
        # ---- 撤销：递归到兄弟分支前数据结构必须干净 ----
        for i in added:
            add(i, -1)                       # 只撤自己加过的，比整棵树清零快得多
        stack.append((vl, vm, ilo, p - 1, left))     # 左分支拿前缀那段元素
        stack.append((vm + 1, vr, p, ihi, right))    # 右分支拿剩下那段
    return ans

自测（与 sorted(a[l:r+1])[k-1] 暴力对拍 300 组随机小数据，全部一致）。

带修改的版本¶

数组会被单点修改时，元素集合不再是「按值排序的一段前缀」，必须真的维护一个操作序列：

操作类型	在整体二分里的行为
插入值 \(v\) 到位置 \(p\)	若 \(v \le v_m\) 则塞进树状数组，归入左半；否则归入右半
删除位置 \(p\) 的值 \(v\)	同上，但塞的是 \(-1\)
询问 \((l,r,k)\)	查区间和 \(c\)，按 \(c\) 与 \(k\) 分流

「单点修改」拆成「删旧值 + 插新值」两个操作，于是带修区间第 \(k\) 小（P2617）就和静态版共用同一份框架。复杂度 \(O((n+q)\log V\log n)\)，和主席树 + 树套树同阶但常数小得多—— 这是整体二分在 C++ 里最大的卖点。

整体二分的适用信号¶

信号	说明
多个询问，每个都可以独立二分答案	这是前提
判定函数需要一个数据结构，且「加入元素」的代价可以被多个询问共享	这是收益来源
不强制在线	硬性要求
判定关于二分的量单调	与普通二分同一个要求

⚠️ 反例：可行性不单调就不能整体二分。比如 BISHI91 拼接木棍（二分的反例题）—— 可行性关于 \(L\) 不单调（需 \(L \mid T\)），连普通二分都不能用，整体二分更无从谈起。 整体二分只是把「多个二分」批处理，它不能让不能二分的东西变得能二分。

2　什么会毁掉离线分治¶

根因：「区间加」是一个会破坏值域有序性的操作。

修改类型	对「值域数据结构」的影响	能否离线分治
单点赋值 / 单点加	只动一个元素 → 拆成「删旧值 + 插新值」	✅ CDQ / 整体二分都行
区间加	动 \(O(r-l)\) 个元素的值	❌ 拆不开
区间赋值	同上	❌

而分块之所以能救命，正是因为它找到了一个局部不变量：

整块加法只是「整体平移」，不改变块内元素的相对顺序。 于是块内的排序副本可以完全不动，只记一个偏移量 off[b]，查询时把阈值反向平移成 \(x - \text{off}[b]\) 即可。

一个具体的反例是 BISHI129「区间增量与区间小于计数」：它看起来非常像整体二分的模板题（多询问、涉及值的比较、允许离线），但修改是区间加，拆不成单点操作，三条离线路全堵死。它的正解是分块 + 块内排序副本，完整实现见分块与平衡树与有序集合。

3　本章速查¶

要点	结论
整体二分是什么	把 \(q\) 个独立的二分按层同步推进，共享「塞元素」的代价
递归对象	（值域区间, 元素集合, 询问集合）
复杂度	\(O((n+q)\log V\log n)\)
坑一	归入右半时 `k -= c`
坑二	每层结束必须撤销数据结构（第一大 bug）
静态数组的简化	「值 \(\le v_m\) 的元素」在按值排序的列表里是一段前缀 → 用下标区间表示
带修版怎么做	「单点修改」拆成「删旧值 + 插新值」两个操作
前提	多个询问 + 判定单调 + 不强制在线
不能做什么	不能让不能二分的东西变能二分（如 BISHI91）
「区间加」为什么毁掉离线分治	它同时改变 \(O(r-l)\) 个元素的值，拆不成单点操作
分块为什么能救 BISHI129	整块加只是整体平移，不改变块内相对顺序

数据规模 → Python 现实性
整体二分（静态区间第 \(k\) 小），\(n=q\le10^5\)
整体二分，\(n=q\le10^4\)
带修区间第 \(k\) 小，\(n=q\ge10^5\)
分块 + 块内排序副本，\(n=q\le10^5\)

归并分治与 CDQ 的速查条目在 CDQ 分治章末。

第 118A 章 整体二分¶

1 整体二分¶