K-D Tree

概述

K-D Tree 是按维度轮流划分的二叉空间树，支持 k 维空间的范围查询、最近邻查询等操作。建树时交替选取某一维、以中位数为界把点集划成两半，使整棵树大致平衡；查询时借每棵子树的包围盒做剪枝，跳过不可能含答案的分支，避免遍历全部点。在二维情形下，范围查询的复杂度约为根号 n 量级。它适合处理带坐标的静态几何统计问题，如矩形区域计数、平面最近点对，是替代树套树的一种常见思路。附 P4148 作为例题。

参考资料

• K-D Tree - OI Wiki

简介

K-D Tree 是按维度轮流划分的二叉空间树，支持 $k$ 维空间的范围查询、最近邻查询等。建树时交替选某一维取中位数划分；查询时用每棵子树的包围盒做剪枝。在二维下，范围查询的复杂度约为 $O(\sqrt n)$。

例题

洛谷 P4148 简单题

在线维护平面上的点集，支持插入一个点、查询某矩形区域内所有点的权值和（强制在线）。