【理论】整体二分思想

整体二分是解决数据结构问题的一种重要方式。

二分是较为基础的内容，在此不作提及，我们直接从一个数据结构问题的角度引入。

现在有一个数据结构问题，其维护的结构的大小为 \(n\)，有 \(q\) 个询问，且询问的答案具有可二分性，则整体二分的过程如下。

首先将所有询问离线，然后设函数 \(solve(S,l,r)\)，表示目前处理的询问集合为 \(S\)，且这些询问最终的答案在 \([l,r]\) 之间。

考虑对答案区间 \([l,r]\) 分为 \([l,mid]\) 以及 \([mid+1,r]\) 两部分考虑，那么我们接下来需要对 \(S\) 中的每个询问都判断其答案是否 \(>mid\)，并基于此进一步将集合划分为 \(S_1,S_2\) 并递归进行 \(solve(S_1,l,mid)\) 以及 \(solve(S_2,mid+1,r)\)。

最终，当 \(l=r\) 时，对应集合 \(S\) 中所有询问的答案也就出来了。

考虑一下将每个 \(S\) 划分为 \(S_1,S_2\) 的过程，判断每个询问的答案是否 \(>mid\) 对应的是数据结构中的一次查询，而在此之前，我们需要把 \([l,mid]\) 对应的数据结构状态维护出来，而这相当于数据结构中的多个修改。

我们接下来要考虑时间复杂度的问题，观察到整体二分的过程类似于线段树的结构，设答案值域为 \(v\)，数据结构查询复杂度 \(O(k)\)，修改复杂度 \(O(p)\)，可以得到如下性质：

• 每个询问被 \(solve\) 次数的级别为 $ O(\log v)$ 次，相当于每个询问让数据结构被查询 \(O(\log v)\) 次，数据结构查询总复杂度 \(O(kq\log v)\)。

• 答案值域上的每个点被 \(O(\log v)\) 个答案区间 \([l,r]\) 包含，相当于值域上的每个点都要被加入数据结构当中 \(O(\log v)\) 次，考虑每个点可能对应多个单点加，但值域上所有点对应单点加个数的总和是 \(O(n)\)，所以数据结构修改总复杂度 \(O(pn\log v)\)。

这样的话，整体二分的总复杂度为 \(O((kq+pn)\log v)\)。

在大多数情况 \(k=p=\log n,n=q\) 时，复杂度为 \(O(n\log^2n)\)。

值得一提的是，整体二分中的数据结构维护在某些题目中可以通过持续离散化后差分——前缀和的方式快速维护以此做到 \(O(n\log n)\) 的复杂度，同时整体二分在某些时候可以支持修改，具体内容会在应用篇详细解释。