AC. 梦想

frank_c1

[BZOJ 4066] 简单题

发布于2016年02月21日 | 暂无评论 | 558阅读 | KD树,数据结构

题目描述

[BZOJ 2683] 简单题。本题要求强制在线。

题目解析

终于来填坑啦!

离线版的是CDQ分治经典题,在线版好像不能这样搞。于是我们找来一些比较有趣的数据结构,本题采用KD树。

KD树是一种索引高维向量的一种数据结构,它按照维度顺序不断划分高维空间,每一个数据点保存了它所表示的高维向量,它所划分空间的范围,以及它的左右儿子,当然也可以维护一些别的信息(如权值)。这种数据结构支持一般的插入、删除、查询;更高级的,还可以完成在高维空间寻找最近邻结点以及K近邻结点的操作。

在二维、三维空间下,KD树的效率尚可令人接受;在更高维空间下,KD树就比较鸡肋了。本题是在二维空间内,如果是随机数据,朴素的KD树还是可以较快跑出的。然而我们发现,朴素的KD树就像二叉搜索树,构造一些极限数据就可以使复杂度直线上升,TLE。于是我们需要寻求一些平衡的策略。二维情况下,貌似不能像许多平衡树那样转来转去,又看到网上有说要求方差什么的,太麻烦,如果在考场上肯定会被搞晕。可以采用替罪羊树的思想,不平衡达到一定程度后暴力重构。不过平衡因子比较难确定,我觉得黄学长的实现就很直观(膜一膜),设定一个阈值,比如说插入操作每达到8000次就暴力重构整棵树,一定程度上保证树的平衡,从而保证复杂度。二维情形下单次操作复杂度为O( \sqrt {n}),总复杂度O(n \sqrt {n}),空间复杂度O(n)

最后吐槽一句,简单题真是一点也不简单。