题目链接

4066传送门

题解

KD_TREE
插入: 新建一个节点,坐标为 (x, y),权值为 A,插入到 K-D Tree 中。
查询: 将之前的目标点改成目标矩形区域就好了。
如果接下来要查的区域完全被包含于目标矩形区域,那就跟线
段树区间查询一样直接返回区域和就好了;
否则,如果接下来要查的区域与目标区域有交集,就往下查,
否则不查。

拓展

这个题怎么构造数据卡掉别人
在一个区域内各种加点 然后导致KD_TREE不平衡

改进

我们采用替罪羊式重构

代码