K-D Tree

参考资料

• K-D Tree - OI Wiki

简介

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

例题

洛谷 P4148 简单题

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