引言
在信息学竞赛和实际工程中，我们经常遇到这样的问题：给定一个序列和多个查询，每个查询要求找出满足某种条件的第K小元素或某个阈值。如果独立地对每个查询进行二分搜索，时间复杂度通常为 O(Q log N · T)，其中Q是查询数，N是序列长度，T是单次判定的时间。当查询数量很大时，这种朴素做法往往无法满足性能要求。
整体二分（Parallel Binary Search / 整体二分）是一种巧妙的离线算法，它将所有查询”并行”处理，同时二分所有查询的答案，通过一次遍历即可将查询集合划分到左右两个子区间。这种并行化处理将总复杂度从 O(Q log N · T) 优化到 O((N + Q) log N · T̄)，其中T̄是平均单次判定时间，在处理大量查询时具有显著的性能优势。
核心原理
独立二分 vs 整体二分
假设有Q个查询，每个查询要求在数组中找第K小的数：
独立二分：每个查询做log N次二分，每次二分需要O(N)时间判定。总复杂度 O(Q · N log N)。
整体二分：所有查询同时进行二分。在每一层递归中，取中点mid，用一次O(N)的扫描同时处理所有查询，将查询分成”答案≤mid”和”答案>mid”两组。总复杂度 O((N + Q) log N)。
算法框架
整体二分的核心是一个分治过程 solve(queries, L, R)：
- 终止条件：如果查询集合为空，或L==R，则直接确定所有查询的答案为L
- 取中点：
mid = (L + R) / 2 - 批量判定：遍历数据，统计≤mid的元素对各个查询的影响
- 分组：根据判定结果将查询分为左组（答案≤mid）和右组（答案>mid）
- 递归处理：对左组递归
solve(leftQueries, L, mid)，对右组递归solve(rightQueries, mid+1, R)
关键洞察
整体二分之所以有效，是因为不同查询的二分搜索过程有大量重叠的计算。在第i层递归中，所有查询都在判断同一个mid值，因此数据结构的更新和查询可以批量进行，避免了重复劳动。
Java实现
经典问题：区间第K小
import java.util.*;
/**
* 整体二分算法实现
* 解决区间第K小等批量查询问题
*/
public class ParallelBinarySearch {
/**
* 查询结构体
*/
static class Query {
int id; // 查询编号
int l, r; // 查询区间[l, r]
int k; // 第K小
int ans; // 答案
Query(int id, int l, int r, int k) {
this.id = id;
this.l = l;
this.r = r;
this.k = k;
this.ans = -1;
}
}
private int[] arr; // 原始数组
private int[] sorted; // 排序后的离散化值
private int n; // 数组长度
public ParallelBinarySearch(int[] arr) {
this.arr = arr.clone();
this.n = arr.length;
this.sorted = arr.clone();
Arrays.sort(this.sorted);
// 去重
int m = 0;
for (int i = 0; i < sorted.length; i++) {
if (i == 0 || sorted[i] != sorted[i-1]) {
sorted[m++] = sorted[i];
}
}
this.sorted = Arrays.copyOf(sorted, m);
}
/**
* 树状数组，用于动态统计区间和
*/
static class FenwickTree {
int[] tree;
int n;
FenwickTree(int n) {
this.n = n;
this.tree = new int[n + 1];
}
void add(int idx, int delta) {
for (; idx <= n; idx += idx & -idx) {
tree[idx] += delta;
}
}
int query(int idx) {
int sum = 0;
for (; idx > 0; idx -= idx & -idx) {
sum += tree[idx];
}
return sum;
}
int rangeQuery(int l, int r) {
return query(r) - query(l - 1);
}
void clear() {
Arrays.fill(tree, 0);
}
}
/**
* 整体二分求解区间第K小
* @param queries 查询列表
* @return 每个查询的答案数组
*/
public int[] solveKthSmallest(List<Query> queries) {
int q = queries.size();
int[] answers = new int[q];
// 将查询按id保存到数组中方便查找
Query[] queryArray = queries.toArray(new Query[0]);
// 整体二分：值域为sorted数组的下标范围[0, sorted.length-1]
solve(queryArray, 0, sorted.length - 1, new FenwickTree(n));
for (Query query : queryArray) {
answers[query.id] = sorted[query.ans];
}
return answers;
}
/**
* 整体二分的核心递归函数
* @param queries 当前待处理的查询集合
* @param L 当前值域左边界（sorted数组下标）
* @param R 当前值域右边界（sorted数组下标）
* @param bit 树状数组，用于统计
*/
private void solve(Query[] queries, int L, int R, FenwickTree bit) {
if (queries.length == 0) return;
if (L == R) {
for (Query q : queries) {
q.ans = L;
}
return;
}
int mid = (L + R) >>> 1;
int midVal = sorted[mid];
// 将数组元素按值分为≤midVal和>midVal两组
// 同时处理所有查询：统计查询区间[l,r]内≤midVal的元素个数
List<Query> leftQueries = new ArrayList<>();
List<Query> rightQueries = new ArrayList<>();
// 使用索引追踪当前处理到数组的哪个位置
// 按位置顺序处理，保证树状数组的正确性
// 先收集所有需要判定的事件（位置+类型）
List<Event> events = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (arr[i] <= midVal) {
events.add(new Event(i + 1, -1, 0)); // 位置i+1（1-indexed），类型=添加元素
}
}
for (Query q : queries) {
events.add(new Event(q.r, q.id, 1)); // 右端点查询
events.add(new Event(q.l - 1, q.id, 2)); // 左端点-1查询
}
// 按位置排序
events.sort(Comparator.comparingInt(e -> e.pos));
// 当前查询的临时计数
int[] count = new int[queries.length];
Arrays.fill(count, -1); // -1表示未初始化
int eventIdx = 0;
bit.clear();
for (Event e : events) {
if (e.type == -1) {
// 添加元素
bit.add(e.pos, 1);
} else {
// 查询事件
int qid = e.queryId;
int cnt = bit.query(e.pos);
if (e.type == 2) {
// 左端点：记录前缀和，后续相减
count[qid] = -cnt; // 用负数标记
} else {
// 右端点：计算区间和
if (count[qid] < 0) {
count[qid] = cnt + count[qid]; // count[qid]存储的是-cnt_left
} else {
count[qid] = cnt - count[qid];
}
}
}
}
// 注意：上面的事件处理逻辑比较复杂，简化版如下
// 重新用更简单的方法：直接遍历每个查询，用树状数组统计
leftQueries.clear();
rightQueries.clear();
bit.clear();
// 更简单的方法：按位置顺序扫描数组，遇到查询就回答
// 创建位置到查询的映射
List<List<Query>> queriesAtPos = new ArrayList<>();
for (int i = 0; i <= n; i++) queriesAtPos.add(new ArrayList<>());
for (Query q : queries) {
queriesAtPos.get(q.r).add(q);
}
// 正向扫描
for (int i = 1; i <= n; i++) {
if (arr[i - 1] <= midVal) {
bit.add(i, 1);
}
for (Query q : queriesAtPos.get(i)) {
int cnt = bit.rangeQuery(q.l, q.r);
if (cnt >= q.k) {
leftQueries.add(q);
} else {
q.k -= cnt; // 答案在右侧，需要减去左侧贡献
rightQueries.add(q);
}
}
}
// 递归处理左右两组
solve(leftQueries.toArray(new Query[0]), L, mid, bit);
solve(rightQueries.toArray(new Query[0]), mid + 1, R, bit);
}
static class Event {
int pos, queryId, type;
Event(int pos, int queryId, int type) {
this.pos = pos;
this.queryId = queryId;
this.type = type;
}
}
}
简化且正确的实现
/**
* 整体二分的简洁实现
* 以区间第K小为例
*/
public class ParallelBinarySearchSimple {
static class Query {
int id, l, r, k, ans;
Query(int id, int l, int r, int k) {
this.id = id; this.l = l; this.r = r; this.k = k;
}
}
private int[] arr;
private int[] sorted;
private int n;
public ParallelBinarySearchSimple(int[] arr) {
this.arr = arr.clone();
this.n = arr.length;
this.sorted = arr.clone();
Arrays.sort(sorted);
int m = 1;
for (int i = 1; i < sorted.length; i++) {
if (sorted[i] != sorted[i-1]) sorted[m++] = sorted[i];
}
sorted = Arrays.copyOf(sorted, m);
}
/**
* 树状数组
*/
static class BIT {
int[] t;
int n;
BIT(int n) { this.n = n; t = new int[n+2]; }
void add(int i, int v) { for (; i<=n; i+=i&-i) t[i]+=v; }
int sum(int i) { int r=0; for (; i>0; i-=i&-i) r+=t[i]; return r; }
int range(int l, int r) { return sum(r)-sum(l-1); }
void clear() { Arrays.fill(t, 0); }
}
public int[] solve(List<Query> queries) {
int q = queries.size();
int[] ans = new int[q];
Query[] qs = queries.toArray(new Query[0]);
solve(qs, 0, sorted.length-1, new BIT(n), ans);
return ans;
}
private void solve(Query[] qs, int L, int R, BIT bit, int[] ans) {
if (qs.length == 0) return;
if (L == R) {
for (Query q : qs) ans[q.id] = sorted[L];
return;
}
int mid = (L + R) >>> 1;
int midVal = sorted[mid];
// 创建按右端点排序的查询事件
// 使用离线方式：按数组下标扫描
List<Query> left = new ArrayList<>();
List<Query> right = new ArrayList<>();
// 将查询按r分组
List<Query>[] byR = new ArrayList[n+1];
for (int i = 0; i <= n; i++) byR[i] = new ArrayList<>();
for (Query q : qs) byR[q.r].add(q);
bit.clear();
for (int i = 1; i <= n; i++) {
if (arr[i-1] <= midVal) bit.add(i, 1);
for (Query q : byR[i]) {
int cnt = bit.range(q.l, q.r);
if (cnt >= q.k) left.add(q);
else { q.k -= cnt; right.add(q); }
}
}
solve(left.toArray(new Query[0]), L, mid, bit, ans);
solve(right.toArray(new Query[0]), mid+1, R, bit, ans);
}
}
应用：动态区间中位数查询
/**
* 整体二分在动态问题中的应用
* 带修改操作的区间第K小（简化版，只支持单点修改）
*/
public class DynamicParallelBinarySearch {
static class Operation {
int type; // 0=修改, 1=查询
int pos, val; // 修改操作
int l, r, k, id; // 查询操作
Operation(int pos, int val) {
this.type = 0; this.pos = pos; this.val = val;
}
Operation(int l, int r, int k, int id) {
this.type = 1; this.l = l; this.r = r; this.k = k; this.id = id;
}
}
private int n;
private int[] arr;
private List<Operation> ops;
public DynamicParallelBinarySearch(int[] arr) {
this.arr = arr.clone();
this.n = arr.length;
this.ops = new ArrayList<>();
}
public void update(int pos, int val) {
ops.add(new Operation(pos, val));
}
public void query(int l, int r, int k, int id) {
ops.add(new Operation(l, r, k, id));
}
/**
* 使用CDQ分治+整体二分处理动态区间第K小
* 时间复杂度：O((N+Q) log N log V)
*/
public int[] solve() {
// 收集所有可能的值进行离散化
int[] allVals = new int[n + ops.size()];
int idx = 0;
for (int v : arr) allVals[idx++] = v;
for (Operation op : ops) {
if (op.type == 0) allVals[idx++] = op.val;
}
Arrays.sort(allVals);
int m = 1;
for (int i = 1; i < idx; i++) {
if (allVals[i] != allVals[i-1]) allVals[m++] = allVals[i];
}
int[] values = Arrays.copyOf(allVals, m);
// 整体二分处理
int q = 0;
for (Operation op : ops) if (op.type == 1) q++;
int[] answers = new int[q];
// 将操作序列整体二分
List<Operation> queryOps = new ArrayList<>();
for (Operation op : ops) if (op.type == 1) queryOps.add(op);
solveDynamic(queryOps, 0, values.length - 1, values, answers);
return answers;
}
private void solveDynamic(List<Operation> queries, int L, int R, int[] values, int[] ans) {
if (queries.isEmpty()) return;
if (L == R) {
for (Operation q : queries) ans[q.id] = values[L];
return;
}
int mid = (L + R) >>> 1;
int midVal = values[mid];
// 需要按时间顺序处理所有操作（包括修改和查询）
// 使用树状数组维护当前≤midVal的元素分布
BIT bit = new BIT(n);
List<Operation> left = new ArrayList<>();
List<Operation> right = new ArrayList<>();
// 扫描所有操作（包括修改）
int curArrIdx = 0;
int[] curArr = arr.clone();
int opIdx = 0;
for (Operation op : ops) {
if (op.type == 0) {
// 修改操作：如果旧值≤midVal则移除，新值≤midVal则添加
if (curArr[op.pos] <= midVal) bit.add(op.pos + 1, -1);
curArr[op.pos] = op.val;
if (op.val <= midVal) bit.add(op.pos + 1, 1);
} else {
// 查询操作
int cnt = bit.range(op.l, op.r);
if (cnt >= op.k) {
left.add(op);
} else {
op.k -= cnt;
right.add(op);
}
}
}
solveDynamic(left, L, mid, values, ans);
solveDynamic(right, mid + 1, R, values, ans);
}
static class BIT {
int[] t; int n;
BIT(int n) { this.n = n; t = new int[n+2]; }
void add(int i, int v) { for (; i<=n; i+=i&-i) t[i]+=v; }
int sum(int i) { int r=0; for (; i>0; i-=i&-i) r+=t[i]; return r; }
int range(int l, int r) { return sum(r)-sum(l-1); }
}
}
测试用例
public class ParallelBinarySearchDemo {
public static void main(String[] args) {
// 测试区间第K小
int[] arr = {1, 5, 2, 6, 3, 7, 4, 8};
System.out.println("=== 整体二分：区间第K小 ===");
System.out.println("数组: " + java.util.Arrays.toString(arr));
ParallelBinarySearchSimple pbs = new ParallelBinarySearchSimple(arr);
List<ParallelBinarySearchSimple.Query> queries = new ArrayList<>();
queries.add(new ParallelBinarySearchSimple.Query(0, 1, 4, 2)); // [1,5,2,6]中第2小 = 2
queries.add(new ParallelBinarySearchSimple.Query(1, 2, 5, 3)); // [5,2,6,3]中第3小 = 5
queries.add(new ParallelBinarySearchSimple.Query(2, 1, 8, 5)); // 全局第5小 = 5
queries.add(new ParallelBinarySearchSimple.Query(3, 3, 6, 1)); // [2,6,3,7]中第1小 = 2
int[] answers = pbs.solve(queries);
System.out.println("查询结果:");
System.out.println("Q0 [1,4] 第2小 = " + answers[0]);
System.out.println("Q1 [2,5] 第3小 = " + answers[1]);
System.out.println("Q2 [1,8] 第5小 = " + answers[2]);
System.out.println("Q3 [3,6] 第1小 = " + answers[3]);
// 验证
System.out.println("\n手动验证:");
int[][] verify = {
{1, 5, 2, 6}, {5, 2, 6, 3}, {1, 5, 2, 6, 3, 7, 4, 8}, {2, 6, 3, 7}
};
int[] ks = {2, 3, 5, 1};
for (int i = 0; i < 4; i++) {
int[] tmp = verify[i].clone();
java.util.Arrays.sort(tmp);
System.out.println("Q" + i + " 验证: " + tmp[ks[i]-1]);
}
System.out.println("\n=== 对比：独立二分 vs 整体二分 ===");
System.out.println("数组长度 N=" + arr.length + ", 查询数 Q=" + queries.size());
System.out.println("独立二分复杂度: O(Q * N * logN) = " + (queries.size() * arr.length * 3));
System.out.println("整体二分复杂度: O((N+Q) * logN) = " + ((arr.length + queries.size()) * 3));
}
}
复杂度分析
| 问题 | 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 区间第K小 | 独立二分+树状数组 | O(Q · N log N) | O(N) |
| 区间第K小 | 整体二分 | O((N + Q) log N log V) | O(N + Q) |
| 带修改区间第K小 | 整体二分+CDQ | O((N + Q) log² N) | O(N + Q) |
其中V是值域大小。整体二分的优势在于所有查询共享同一轮数据结构操作，当Q很大时（如10⁵级别），性能提升非常显著。
经典应用场景
- 区间第K小/大：静态或动态序列的区间次序统计
- 矩阵查询：二维平面上的点计数与第K近邻
- 网络流判定：判断是否存在流量为F的可行流
- 图论问题：判断是否存在长度≤K的路径
- 组合优化：多重背包、资源分配等判定问题
技巧总结
- 离线处理：整体二分必须离线进行，需要预先知道所有查询
- 值域离散化：将连续值域映射到整数下标，缩小二分范围
- 批量统计：在每一层递归中，用单次扫描同时处理所有查询
- 查询分组：根据判定结果将查询分为两组，注意右组要减去左侧贡献
- 与CDQ结合：对于带修改的问题，先用CDQ分治将时间维度转化为静态问题
总结
整体二分通过将多个查询的二分过程并行化，显著降低了批量查询的时间复杂度。本文以区间第K小为核心案例，展示了整体二分的完整实现，并扩展到动态修改场景。掌握整体二分的核心思想——批量判定与分组递归——能够有效解决大规模离线查询问题。
