整数下限和上限查询的快速数据结构？

Question

我必须保留一个数字列表,数量高达100,000 ...

如果数据是(例如)

1, 4, 9, 12, 20, 35, 52, 77, 91

并且我查询一个数字,比方说27,我想要紧接在27之前的数字,在列表中可用,所以这将是:20

数据也会经常被修改,比如大量的插入和删除.

目前我正在使用stl::set加上

set<int>iterator it = lower_bound(values.begin(), values.end(), n);

所以

*it = 35 并且it--,我得到20 ...但这还不够快,查询的数量很大,高达500,000 ..其中包括更改我的值或查找值.

请给我一些指示.

Answer 1

我想到了一些不同的想法.

对于初学者来说,有一个专门的数据结构就是这个问题,称为van Emde Boas树,它存储一些固定范围[0,U]中的整数,并支持O(log log U)时间内的后继和前任搜索.这比使用标准二叉搜索树进行比较要快得多.如果您知道要存储的整数的上限,则此结构可能会使您获得更高的性能.还有其他相关的结构,如y-fast trie,也可以在这里使用.

其次,如果您拥有的查询是统一分布的,您可能希望构建自己的二叉搜索树,该树已经过优化,可以最大限度地减少整体查找的节点数.这种搜索树被称为最优二叉搜索树,并且存在用于在O(n log n)时间内近似它们的快速算法.在之前的这个问题中,我详细介绍了一种方法.这种预处理可以为您提供更快的查找速度,因为树是专门为优化查找时间而构建的.或者,您可以查看splay树,它们具有相当的性能.

希望这可以帮助!