获取O（对数n）时间内平均值的数据结构

Question

我需要设计一个数据结构的想法，它可以在
O（logn）时间内插入、删除和获取平均值（a，b）。getmean（a，b）是[a，b]中所有数字x的算术平均值

我的想法-
一般来说，如果我们将数据存储在像AVL树这样的平衡搜索树中，插入和删除操作可以在O（logn）时间内完成。但是为了在O（logn）时间内求解getmean（a，b），我们需要存储一些额外的信息。为了计算平均值，我们可以做以下操作：
递归地进行深入遍历。如果当前元素

Answer 1

让树中的每个节点存储它下面元素的计数和和。

然后，您可以以对数（n）步数计算任何范围的计数和总和。从中你可以计算出平均值。

在一个范围内计算这些统计数据的诀窍是，如果我在一个我知道完全在我的范围内的节点上，那么我可以查看它的统计数据，而不必访问该范围。这意味着我只需要探索范围的边缘。假设是一棵树，这里是未经测试的Python，您可以将其视为伪代码。

def find_min (node):
    if node.left is not None:
        return find_min(node.left)
    else:
        return node.value

def find_max (node):
    if node.right is not None:
        return find_min(node.right)
    else:
        return node.value

def find_count_sum_range(node, start, end, lower=None, upper=None):
    # Calculate bounds if not found.
    if lower is None:
        lower = find_min(node)

    if upper is None:
        upper = find_min(node)

    # Shortcut if this node is entirely in the range.
    if start <= lower and upper < end:
        return (node.count, node.sum)

    # Initialize
    count_left = sum_left = 0
    count_this = sum_this = 0
    count_right = sum_right = 0

    # Do we find range to the left?
    if start <= node.value and node.left is not None:
        (count_left, sum_left) = find_count_sum_range(
            node.left, start, end, lower, node.value)

    # Do we find range to the right?
    if node.value < end and node.right is not None:
        (count_left, sum_left) = find_count_sum_range(
            node.left, start, end, node.value, upper)

    # Is this node in range?
    if start <= node.value and node.value < end:
        (count_this, sum_this) = (1, node.value)

    # Add up our answer
    return (
        count_left + count_this + count_right,
        sum_left + sum_this + sum_right
    )

我个人会发现使用跳过列表比使用AVL树更容易实现，但那是因为我很懒，不想仔细考虑树操作。但即使在那里，技巧仍然是一样的——只要你能读出一个范围的计数和总和，就不要访问该范围内的节点。