我有一些关于扩充数据结构的问题:
令 S = {k1, . . . , kn} 是一组数字。设计一个高效的 S的数据结构，支持以下两种操作:
Insert(S, k) 插入 将 k 数放入 S(你可以假设 k 还没有包含在 S 中)，以及 TotalGreater(S, a) 它返回所有大于 a 的键 ki ∈ S 的总和，即 P ki∈S, ki>a ki 。
讨论两个操作的运行时间并给出TotalGreater(S, a)的伪代码(不要给出Insert(S, k)的伪代码).
我不明白该怎么做，我想在 RB 树中添加一个名为 sum 的额外字段，但后来它不起作用，因为有时我只需要左节点的总和，有时我也需要正确节点的总和。
所以我想添加 2 个字段，称为 leftSum 和 rightSum，如果当前节点 > GivenValue，则将子节点总和的缓存值添加到当前总和值。
有人可以帮我解决这个问题吗？
最佳答案
您可以向每个节点添加一个变量size，这是以该节点为根的子树中的节点数。当找到具有大于值 a 的最小值的节点时，在通往该节点的路径上可能会发生两种情况:您可以向左或向右走。每次向左移动时，都会将右 child 的大小 + 1 添加到运行总数中。每次你走对了，你什么都不做。
有两个终止条件。 1) 我们找到一个包含精确值 a 的节点，在这种情况下，我们将其右 child 的大小添加到总数中。 2) 我们到达一片叶子，在这种情况下，如果它大于 a，我们加 1，如果它更小，则什么都不加。
关于algorithm - 求和的RB树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29194071/