Day 067-Q5 — 動的平面最近傍探索（KD-Tree + オンライン点追加）

問題

$Q$ 個のオンラインクエリを処理せよ。

• クエリ型 1: 1 x y — 点 $(x, y)$ を集合に追加する。
• クエリ型 2: 2 x y — 集合内の点で $(x, y)$ に最も近い点のユークリッド距離の2乗を求めよ。集合が空なら -1 を出力せよ。

入出力例

6
1 3 4
1 1 1
2 2 2
1 7 8
2 5 5
2 0 0

2
8
2

(2,2)→(1,1)距離^2=2。(5,5)→(3,4)距離^2=8。(0,0)→(1,1)距離^2=2。

概念図: KD-Tree + Logarithmic Rebuilding

ヒント（段階的開示）

class LogKDTree:
    def __init__(self):
        self.trees = {}  # size -> (kdtree, points)

    def add(self, x, y):
        size = 1
        pts = [(x, y)]
        while size in self.trees:
            old = self.trees.pop(size)[1]
            pts += old
            size *= 2
        self.trees[size] = (self._build(pts, 0), pts)

    def nearest(self, qx, qy):
        best = inf
        for size, (tree, _) in self.trees.items():
            best = self._query(tree, qx, qy, best)
        return best if best < inf else -1

模範解答 (Python)

コピーimport sys
from math import inf
input = sys.stdin.readline

class LogKDTree:
    def __init__(self):
        self.trees = {}
        self.total = 0

    def _build(self, pts, depth):
        if not pts:
            return None
        axis = depth % 2
        pts.sort(key=lambda p: p[axis])
        mid = len(pts) // 2
        node = [pts[mid], None, None,
                min(p[0] for p in pts), max(p[0] for p in pts),
                min(p[1] for p in pts), max(p[1] for p in pts)]
        node[1] = self._build(pts[:mid], depth + 1)
        node[2] = self._build(pts[mid+1:], depth + 1)
        return node

    def _box_dist(self, node, qx, qy):
        dx = max(0, node[3] - qx, qx - node[4])
        dy = max(0, node[5] - qy, qy - node[6])
        return dx * dx + dy * dy

    def _query_tree(self, node, qx, qy, best):
        if node is None:
            return best
        px, py = node[0]
        d = (px - qx) ** 2 + (py - qy) ** 2
        best = min(best, d)
        children = []
        if node[1]: children.append((node[1], self._box_dist(node[1], qx, qy)))
        if node[2]: children.append((node[2], self._box_dist(node[2], qx, qy)))
        children.sort(key=lambda x: x[1])
        for child, bd in children:
            if bd < best:
                best = self._query_tree(child, qx, qy, best)
        return best

    def add(self, x, y):
        size = 1
        pts = [(x, y)]
        while size in self.trees:
            old_pts = self.trees.pop(size)[1]
            pts = pts + old_pts
            size *= 2
        self.trees[size] = (self._build(list(pts), 0), pts)
        self.total += 1

    def nearest(self, qx, qy):
        if self.total == 0:
            return -1
        best = inf
        for size, (tree, pts) in self.trees.items():
            best = self._query_tree(tree, qx, qy, best)
        return best if best < inf else -1

def main():
    sys.setrecursionlimit(400010)
    Q = int(input())
    kd = LogKDTree()
    out = []
    for _ in range(Q):
        line = list(map(int, input().split()))
        if line[0] == 1:
            _, x, y = line
            kd.add(x, y)
        else:
            _, x, y = line
            out.append(kd.nearest(x, y))
    print('\n'.join(map(str, out)))

main()

Step-by-Step 解説

Step 1: 静的 KD-Tree の構築

各次元を交互に分割軸とし、中央値で再帰的に分割する。各ノードにバウンディングボックス（min/max x, min/max y）を保持。

Step 2: 最近傍クエリの枝刈り

クエリ点からノードのバウンディングボックスへの最小距離 $\ge$ 現在の最近傍距離なら枝刈り。近い方の子を先に探索する。

Step 3: Logarithmic Rebuilding

サイズ $2^k$ の静的 KD-Tree を複数管理。追加時は同サイズのツリーを合体（二進数のキャリー操作と同様）。$O(\log N)$ 回再構築、合計 $O(N \log^2 N)$。

Step 4: 計算量

よくあるミス

次のステップ

発展: BBD-Tree（Box Decomposition Tree）による最近傍クエリ $O(\log N)$。関連: 静的 KD-Tree + オフライン再構築（バッチ追加問題）。

自己評価