我有一些关于扩充数据结构的问题：
让s={k1，.……，kn}是一组数字。设计一个高效的
支持以下两种操作的S的数据结构：
插入（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的额外字段，但是它不起作用，因为有时我只需要左节点的和，有时我也需要右节点的和。
所以我想添加两个名为leftsum和rightsum的字段，如果当前节点>givenvalue，那么将子节点和的缓存值添加到当前和值。
有人能帮我一下吗？
最佳答案
您只需向每个节点添加一个变量size，这是根在该节点的子树中的节点数当找到具有大于值a的最小值的节点时，该节点的路径上可能会发生两种情况：您可以向左或向右移动每次向左移动时，都会将右边的子项+1的大小添加到运行总数中每次你做对了，你什么都不做。
终止有两个条件。1）我们找到一个包含精确值a的节点，在这种情况下，我们将其右子节点的大小添加到总数中。2）我们得到一个叶子，在这种情况下，如果它大于a，我们就加1；如果它小于cc>，我们就不加。