如何维护数组，支持随机插入和赋值，以及查询给定间隔内的最大kth数？

Question

问题是在线

详细信息:数组<= 35000的长度、插入数<= 35000、赋值数<= 70000和查询数<= 70000；时间限制: 10s (Java:20)。

我在网上找到的模糊解决方案说，我需要使用替罪羊树来维护间隔，并且在替罪羊树的每个节点中，维护一个函数间隔树来查询k第四大元素。我知道如何做第二步，但我不知道如何做第一步。

Answer 1

假设我们(在语义上)有一个数组，如

0: 31337
1: 42
2: 314159
3: 9000
4: 100   .

我们有一个替罪羊树，其中数组条目是按索引排序的。树的每一个节点都存储了遗留后代的数量，这样我们就可以根据索引进行有效的搜索。(这也使替罪羊实现更加简单。)

               9000(3)
              /       \
         42(1)         100(0)
        /     \
31337(0)       314159(0)

对于每个子树，我们还维护它包含的值的值排序BST。这个BST可以是一个替罪羊树，也有实现选择的左后代计数。

31337: {31337}
42: {42, 31337, 314159}
314159: {314159}
9000: {42, 100, 9000, 31337, 314159}
100: {100}

要插入，我们插入替罪羊树，更新左后裔计数，并在我们走下时将新值插入到BSTs中。如果在线性时间内重建BSTs，则摊销插入成本为O(log ^2n)(证明:每个值都属于O(log ) BSTs，因此每一个接触节点的代偿代价为O(log n)，总共O(log^2 n)，插入到O(Log n) BSTs上的代偿节点为O(log^2 n))。要更新，我们必须从BSTs (O(log^2 n))中删除/插入。

查询路径是事情变得丑陋的地方。识别O(log ) BSTs和以数组段为联合的单例集合是容易的部分。困难的部分实际上是做选择。二进制搜索将产生O(log^3 n)-time查询，因为我们在O(log n)数组中有O(log n)轮的选择，每个选择代价为O(log n)。也许弗雷德里克森-约翰逊算法指出了一个答案，但即使对于数组，它也很复杂。

Answer 2

部分答复：

在这种情况下，性能的基本关键是数据结构(也称为集合)，它支持具有O(log )复杂性(或更好的)的所需操作。

在您的情况下，您需要插入和查找(在您的问题中称为赋值和查询)。

因为您还要求“最大”您需要一个排序的集合。(这就排除了基于具有O(1)复杂性的散列的集合)

所以你应该从二叉树或者尝试开始。

目前不可能给出更多的细节，因为你的回答太含糊。