我正在寻找一种非常高效的想法、概念或数据结构，用于访问保持累积值的集合。
举个例子来说明我的需求:
我有一个值列表(2,3,5)。这个列表在观察累加值时是(2,5,10)。
现在我在列表开头添加1并得到(1,2,3,5)，在累积方面是(1,3,6,11)。
我只需要查看累积值，对1、2、3和5不感兴趣。我需要能够快速插入位置、删除位置，并且所有这些操作都可以快速更新累积数组(最好不需要遍历整个数组并重新计算值)。
有什么想法或提示吗?
@Kristo (评论中写不下): 为了说明负数会使总和值失去意义，请看以下示例。
插入1，然后是-1。和是1，然后是0。(1,-1)//(1,0) 插入3，接着插入-3。和是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: 主要原因是为了能够判断我是否超过了某个值以及在链中的哪个位置。
idx values cumulative operation 3 (2,3,5) (2, 5, 10) 0 (1,2,3,5) (X,X,X,X) 在0处插入1 3 (1,2,3,5) (1,3,6,X) 查找超过5的值 3 (1,2,3,5,4) (1,3,6,X,X) 在4处插入4
使用具有额外属性的二叉搜索树，即节点包含其子树之和。所有操作仍然是O(lg n)。要插入或删除值，您需要执行正常的过程，并更新所有父项的总和。获取总和就像找到包含元素的节点并返回其总和减去其右子节点的总和一样简单。
您可以将值范围分成固定的位范围。例如，3个间隔：
#define NUM (1<<24) // 数据集中的最大值
#define BITS0 8
#define BITS1 8
int cum0[NUM >> (BITS0+BITS1)]; // cum1 的总和
int cum1[NUM >> BITS1]; // 计数的总和
int count[NUM];
int add(id, val) { // 添加一个值
cum0[id >> (BITS0+BITS1)] += val;
cum1[id >> BITS1] += val;
count[id] += val;
}
int cumvalue(int id) { int cum = 0; // 返回索引id处的cum值
for(i = 0; i < (id >> (BITS0+BITS1));i++) cum += cum0[i]; i <<= BITS0;
for(i = (id & ~((1 << (BITS0+BITS1))-1)) >> BITS1; i < (id >> BITS1); i++) cum+= cum1[i]; i <<= BITS1;
for(i = id & ~((1 << BITS1) -1); i < id; i++) cum += count[i];
return cum;
}
我看到有两种简单的方法，都使用基本数据类型 - 列表。
保留原始列表，在每次更改时重新计算累积值。
仅保留累积列表，并使用以下函数进行添加或删除：
Add 2 : (2) 将2添加到空列表中。
Add 3 : (2,5) 将3添加到列表末尾，成为前一个元素（2）的后继元素。
Add 5 : (2,5,10) 将5添加到列表末尾，成为前一个元素（5）的后继元素。
Add 1 at start: (1,3,6,11) 在列表开头添加1，并逐个增加1直到结尾（没有前置元素）。
Add 7 at 2nd position: (1,8,11,14,19) 添加7并逐个增加7直到结尾（没有前置元素）。
Delete 3rd position (The 11) : (1,8,3,8) 获取该值，删除它，将该值添加到其余部分。
这种方式可以保持所有内容的同步，而无需保留原始值。
用C++的术语来说，你能用std::list（在中间轻松插入/删除）或者std::set（始终排序）来存储数据，并使用一个变量来保存总和吗？每次插入/删除时，根据需要修改总和。总和代表了你将要累积列表中的最大数。只有当你超过了魔法数字时，才需要进行一些算法工作来找出你超过的位置。
更新：
根据你提供的新信息，我没有看到很多捷径可用。由于你需要经常在中间插入或删除，所以这暗示了某种链表的方法。你可以通过仅更新已更改的部分来节省一点计算量。假设L是值的列表，n是列表中的目标位置。要在位置n插入值x：
n插入值x + L(n-1)x添加到这个新n之后的所有元素对于删除操作，过程是相同的，只不过你需要从所有后续值中减去相应的数值。这样，只有在插入到开头附近时才需要进行大量的工作。