什么是良好的数据结构来保持累积值？

Question

我正在寻找一个想法,概念或经过验证的数据结构,在访问保持累积值的集合时非常有效.

示例可以更多地阐明我的需求:

我有一个值列表(2,3,5).查看累积值时,此列表将为(2,5,10).

我现在将在列表的开头添加1并获得(1,2,3,5)和累积术语(1,3,6,11).

我只需要查看累积值,我对1,2,3,5并不感兴趣.我需要能够快速插入位置,移除一个位置,所有这一切应该快速更新累积数组(理想情况下,不会遍历整个数组并重新计算值.

任何想法或提示？

@Kristo(太长时间没有加入评论):为了澄清为什么负数会使总和值无意义,请按照这个例子.

插入1后跟-1.Sum为1而不是0.(1,-1)//(1,0)插入3后插入-3.Sum为3然后为0.(1,3,-1,-3)//(1,4,3,0)插入2后插入-2.总和是2然后是0.(1,3,2,-1,-2,-3)//(1,4,6,5,3,0)

如果我的"神奇数字"是4总额不会告诉我是否超过它.

PS:这个的主要原因是能够判断我是否超过了某个值以及链中的哪个位置.

Answer 1

检查累积频率表。

Answer 2

我能想到的唯一优化是对累积列表进行"懒惰"评估.

除了源值列表之外,还要跟踪累积列表中准确的最高位置数.如果您需要一个高于该数字的数字,那么您可以在列表中向上,更新值和索引.

idx  values       cumulative    operation
 3   (2,3,5)      (2, 5, 10)
 0   (1,2,3,5)    (X,X,X,X)     insert 1 at 0 
 3   (1,2,3,5)    (1,3,6,X)     look for value over 5     
 3   (1,2,3,5,4)  (1,3,6,X,X)   insert 4 at 4 

如果你经常在列表的早期添加项目,那么这对你来说不会有很多好处....

Answer 3

使用二叉搜索树，其附加属性是节点包含其子树的总和。所有操作仍然是 O(lg n)。要插入或删除一个值，您可以执行正常的过程，并更新所有父项的总和。获取总和就像找到包含该元素的节点并返回其总和减去其右子节点的总和一样简单。