首先。。要完成这个操作只需要简单的平衡树就行了，手写一个要不了几分钟。。你不介意的话可以用pb_ds，但是我很怀疑这玩意能不能处理好千万级别的操作。如果你想要红黑树的实现，可以在搜索的时候用红黑树+size域。不过红黑树不是特别好找，你搜竞赛用的比较多的treap，splay，sbt什么的肯定一抓一大把，至于维护嘛，size域维护在update写清楚了，各种树之间的差异只是rotate的时机不大一样而已。顺便，如果要并行的话应该skip list更合适一些，这个可以参考redis的实现。至少千万左右的数据塞进内存问题还不大。除非你的内存实在有限。
■网友
不知道你说的频繁变动具体指什么。如果是不断有新数据到来，找出第10到第14位的数据用个最大堆就好了，堆大小为14。超出堆里最大值的数据直接扔掉，否则扔掉最大值新元素入堆————————————————————如果是经常有修改，splay tree或者treap可以达到和红黑树类似的效果，稍慢但写起来难度不可同日而语。
■网友
谢邀，我已经赞了 杨芳斐 的答案，lz按照自己的思路，记录左右子树节点数量就行。不用找啥开源，自己写不算难。稍有些缺陷在于处理并行的话，需要自己设计一下锁，主要考虑好旋转就行。
■网友
开一个大小为20的小根堆真的这么难吗？。。。每次做统计的时候把这个堆flatten到一个数组上再sort一下。。。每次插入是O(logn)的复杂度(n = 20)；每次统计是O(nlogn)的复杂度，有O(n)的额外空间(n = 20)；基本就是常数级的表现啊。。。为什么LS各位大大都用了这么牛逼的算法。。。==UPDATE==刚刚 @杨芳斐 大大指出，数据组的更新不一定是append-only的。所以最小堆的方法并不能得到正确解。/* 可以跳过的部分 { */但是最小堆方法可以得到满意解。因为题主只要求第10和第14大的数，相对非常非常小。如果append多，修改少的话，那么我们可以开一个相对大的小根堆进行处理。不过这个方法不一定能得到正确解，只能在特定情况下得到满意解。所以只讨论到这里。/* } 可以跳过的部分 */LS众位说的线段树、平衡树的解法是正确的，但是相对较难写。我推荐使用分段Hash的方法。我们把千万级数据（10^7）的总量记为n，然后把问题为n的数据切分为sqrt(n)块，分别存储数据范围在, ... 的数据。对于一次添加操作，我们只需要根据数据范围找到对应的数据块，进行一次append操作。 =\u0026gt; O(1)对于一次修改操作，我们也是需要找到数据块， 遍历数据块中的数据，删除对应旧值数据，并再执行一次添加新值操作。 =\u0026gt; O(sqrt(n))对于一次查询操作，我们可以根据每一个数据块的内容数，确定第k大数据在第一个块中，然后在其中做一次求第k大操作。 =\u0026gt; O(sqrt(n))虽然这种方法看起来不是很高大上，但是效果还不错。相对来说比较好写。可以一试。
■网友
数组排个序然后直接找第10到14个有什么问题？
■网友
15位的数组做插入排序都快的不得了吧。。。
■网友
线段树，第k大数
■网友
用插入排序，但是14位以后扔掉。。。这已经是O(n)级别的实现了。

来源：(未知)

【】网址：/a/2020/0401/gd358793.html

标题：查找指定范围的数据使用啥样的算法?