一维点集的动态插入与区间最近点对查询问题求解

核心思路 #

区间内两点的最小差值必然由有序点集中的相邻点对产生，因此我们需要维护一个有序的点集，在查询时仅需遍历区间内的相邻点对即可找到最小值。

具体实现方案 #

1. 数据结构选择 #

使用有序集合/多重集合（如C++的std::multiset、Java的TreeSet）来存储点集：

• 插入操作：O(log n) 时间复杂度，自动维持点的升序排列，支持重复点
• 区间边界查找：通过内置的lower_bound/upper_bound方法，O(log n) 时间定位区间内的首尾点

2. 插入操作（U） #

直接将坐标U插入有序集合，集合会自动处理排序和重复点存储。

3. 查询操作（L R） #

1. 用lower_bound(L)找到第一个≥L的点，用upper_bound(R)找到第一个>R的点，再回退一步得到最后一个≤R的点
2. 如果区间内点的数量不足2，返回无有效差值的标识（如无穷大或-1，依题目要求）
3. 遍历区间内的相邻点对，计算每对的差值，记录最小值

优化方向（针对大数据量场景） #

如果查询频率极高且点集规模很大，可额外维护线段树：

• 线段树的每个节点存储对应区间内的最小相邻差值
• 插入点时，更新该点左右相邻点所在线段树节点的差值信息
• 查询时直接从线段树中获取[L,R]区间的最小差值，时间复杂度O(log n)

代码示例（C++） #

#include <iostream>
#include <set>
#include <climits>
using namespace std;

multiset<int> points; // 用multiset支持重复点

void insert_point(int u) {
    points.insert(u);
}

int query_min_diff(int L, int R) {
    if (points.size() < 2) return INT_MAX;
    
    auto start_it = points.lower_bound(L);
    auto end_it = points.upper_bound(R);
    if (start_it == end_it) return INT_MAX; // 区间内无点
    
    --end_it; // 指向最后一个<=R的点
    if (start_it == end_it) return INT_MAX; // 区间内只有一个点
    
    int min_diff = INT_MAX;
    auto prev_it = start_it;
    ++start_it;
    for (; start_it != next(end_it); ++start_it) {
        int diff = *start_it - *prev_it;
        if (diff < min_diff) min_diff = diff;
        prev_it = start_it;
    }
    // 处理最后一对相邻点
    int last_diff = *end_it - *prev_it;
    if (last_diff < min_diff) min_diff = last_diff;
    
    return min_diff == INT_MAX ? -1 : min_diff;
}

int main() {
    // 初始化点集
    insert_point(1);
    insert_point(6);
    insert_point(7);
    insert_point(10);
    
    cout << query_min_diff(5, 11) << endl; // 输出1
    return 0;
}

内容的提问来源于stack exchange，提问作者Nguyễn Tùng Dương