2026 年省选专题系列五：CDQ 分治与整体二分。

CDQ 分治

离线分治算法，常用于处理三维偏序等问题。

核心思想：

  1. 把问题按某维排序
  2. 递归处理左右两半
  3. 统计左半对右半的贡献
  4. 合并结果

经典应用：

  • 三维偏序问题
  • 动态问题转静态
  • DP 优化

整体二分

把多个查询一起二分处理，降低复杂度。

核心思想：

  1. 把所有查询一起处理
  2. 每次二分答案区间
  3. 根据 mid 划分左右集合
  4. 递归处理

经典应用：

  • 区间第 k 小
  • 带修改区间第 k 小
  • 矩阵第 k 小

省选一对一辅导：151 6522 2880