java - 一种有效的分位数算法/数据结构，允许样本随着时间的推移而增加？

Question

我正在寻找一种有效的分位数算法，该算法允许样本值随着时间的推移而“更新”或替换。
假设我有项目值 1-n .我想将这些放入一个可以有效存储它们的分位数算法中。但是在 future 的某个时间点说，item-i 的值增加。我想删除 item-i 的原始值并将其替换为更新后的值。特定用例适用于样本值随时间增加的流系统。
我见过的最接近这样的东西是 t-Digest data structure .它有效地存储样本值。它唯一缺乏的是删除和替换样本值的能力。
我也看过 Apache Quantiles Datasketch - 它遇到了同样的问题 - 无法移除和更换 sample 。
编辑:更多地考虑这一点，不一定需要删除旧值并插入增加的值。如果存在只能更新值的约束，则可能有一种方法可以更轻松地重新计算内部状态。

Answer 1

如更新时间O(log n)和分位数计算时间 O(log n)对您来说是可以接受的，那么解决方案之一是实现任何类型的自平衡二叉树( Splay tree 、 AVL-tree 、 Red-Black tree )同时保持 HashMap<Key, Node>与树结构并行(或者如果您知道您的键是例如数字 0 到 n-1 ，那么您可以仅将数组用于相同目的)。您还需要为每个给定的节点保留子树中的节点数(这对于所有提到的自平衡树都是可能的 - 这是对节点进行更新的所有方法的一个小补充，例如旋转，等等。)。
使用 key K 更新值的伪代码，新值 V 将是:

Node node = find_node_in_hash_map_by_key(K); # O(1)
delete_node_keeping_subtree_counts_valid(node); # O(log n)
add_new_node_keeping_subtree_counts_valid(K, V); # O(log n)

在 O(log n) 中可以获得分位数 q也是因为每个节点中可用的子树大小，因为它几乎可以让您通过 O(log n) 中的大小访问第 i 个元素。时间。该操作的伪代码如下所示:

# i-th element requested
node = root
while true:
    left = node.left_subtree
    left_count = 0
    if left is not None:
        left_count = left.nodes_count
    if i < left_count:
        node = left # select i-th element in the left subtree
    elif i == left_count:
        return node.value # we have exactly i elements in left subtree, so i-th value is in the current node
    else:
        i -= left_count + 1 # select element i - left_count - 1 from the right subtree
        node = node.right

我不知道针对这种数据结构有什么好的开源 JAVA 解决方案，但是编写自己的 AVL 树并不是那么困难(而且 Splay 树应该是最简单的，只是它们最坏情况的复杂性不是 O(log n) ，而是在平均他们应该是好的)。