BZOJ 1941 SDOI 2010 Hide and Seek K：KD-Tree 最近/最遠鄰查詢

問題描述

平面 n (≤500,000) 個點，曼哈頓距離。對每個點，求其到所有點的最遠距離與最近距離之差的最小值。

KD-Tree 結構

• 構建：遞歸按維度（x/y 交替）中位數分割，構建平衡樹
• 每節點維護子樹邊界框：x0,x1,y0,y1（最小/最大坐標）
• 查詢剪枝：利用邊界框估算到查詢點的最小/最大可能距離

距離估算函數

// 最小可能曼哈頓距離
int disMin(Point p) {
    int d=0;
    if (p.x < x0) d += x0 - p.x;
    if (p.x > x1) d += p.x - x1;
    if (p.y < y0) d += y0 - p.y;
    if (p.y > y1) d += p.y - y1;
    return d;
}
// 最大可能曼哈頓距離
int disMax(Point p) {
    return max(abs(p.x-x0), abs(p.x-x1)) + max(abs(p.y-y0), abs(p.y-y1));
}

查詢算法

遞歸遍歷 KD-Tree，維護全局 _min, _max。優先搜索更有希望的子樹（最小距離搜索 disMin 小的先搜；最大距離搜索 disMax 大的先搜），剪枝條件：子樹估算值無法優於當前最優值則放棄。

完整代碼框架

struct KDNode {
    Point pt; KDNode *ch[2];
    int x0,y0,x1,y1;
    KDNode(Point p): pt(p), ch{nullptr,nullptr}, x0(p.x),y0(p.y),x1(p.x),y1(p.y) {}
    void maintain() {
        for (int d=0; d<2; ++d) if (ch[d]) {
            x0=min(x0,ch[d]->x0); x1=max(x1,ch[d]->x1);
            y0=min(y0,ch[d]->y0); y1=max(y1,ch[d]->y1);
        }
    }
};

KDNode* build(vector& pts, int l, int r, int dim) {
    if (l>r) return nullptr;
    int mid=(l+r)/2;
    nth_element(pts.begin()+l, pts.begin()+mid, pts.begin()+r+1,
        [dim](Point a, Point b){ return dim? a.xch[0] = build(pts, l, mid-1, dim^1);
    node->ch[1] = build(pts, mid+1, r, dim^1);
    node->maintain();
    return node;
}

void queryMin(KDNode* node, Point p, int& best) {
    if (!node) return;
    best = min(best, abs(node->pt.x-p.x)+abs(node->pt.y-p.y));
    int dl = node->ch[0] ? node->ch[0]->disMin(p) : INT_MAX;
    int dr = node->ch[1] ? node->ch[1]->disMin(p) : INT_MAX;
    if (dl < dr) {
        if (dl <= best) queryMin(node->ch[0], p, best);
        if (dr <= best) queryMin(node->ch[1], p, best);
    } else {
        if (dr <= best) queryMin(node->ch[1], p, best);
        if (dl <= best) queryMin(node->ch[0], p, best);
    }
}
// queryMax 類似，用 disMax 且取 max

關鍵點

1. nth_element O(n) 找中位數，構建總時間 O(n log n)
2. 曼哈頓距離邊界估算公式需熟記
3. 剪枝順序：優先探索更優子樹，大幅減少訪問節點數
4. 50 萬數據下，樸素 KD-Tree 平均 O(√n) 查詢，總時間可接受

KD-Tree 是高維最近鄰搜索的經典數據結構，掌握其構建、邊界維護、剪枝查詢三大核心模塊，可解決大規模幾何最近/最遠鄰問題。