这种方法一般用在数据结构中找两个点使得代价最小的这类问题中。本质就是会对答案造成贡献的点对数是 \(O(n \log n)\) 级别的。从而可以暴力找出这些点对转化为二维数点的问题。
例1
有若干个点，区间询问，从中选出两个点，使得这两个点的曼哈顿距离/切比雪夫距离/欧几里得距离最小。
对于曼哈顿距离这类的可以离线后二维数点，但并不好处理区间询问。所以可以参考平面最近点对这道题的思路。这道题是通过在一个 \(d \times d\) 的正方形中至多存在 \(4\) 个距离 \(>=d\) 的点的结论从而可以暴力枚举所有可能的点对，这就说明其实真正可能对答案造成贡献的只有 \(O(n \log n)\) 级别。但是这道题需要先分治求出左右两边的答案再进行合并。这不太好处理区间询问。
所以我们考虑另一种思路，我们从小到大依次枚举 \(2^i\)，判断答案是否 \(\leq 2^i\) 。枚举到 \(i\) 时就说明不存在距离 \(\leq 2^{i-1}\) 的点，那么对于任意一个 $2^i \times 2^i $ 的正方形中最多只会存在 \(O(1)\) 个点 （具体来说，曼哈顿距离时最多 \(4\) 个点，欧几里得距离时最多 \(9\) 个点，只是一个上界）。所以每一个正方形中的每一个点都只有 \(O(1)\) 的点和它构成支配对 （可能成为答案的点对）。所以就只有 \(O(n \log V)\) 的点对数。
具体实现过程就是把坐标系划分成若干个 \(2^k \times 2^k\) 的正方形，对于一个点 \(i\)，我们考虑所有 \(i\) 前面的 \(j\)。那么我们扫描线是从小到大枚举右端点 \(i\)。加入所有的点对 \(j,i\) (\(j<i\))。查询就是所有左端点 \(\geq l\) 的点对的最小值。加入