1

我正在寻找一种数据结构，它可以像段树一样进行范围求和，但可以支持随时添加新数据而无需重建整个树。我相信我可以拼凑一个可以动态处理添加新数据的部分，但它不会很漂亮。

如果有帮助，我将始终“附加”数据，因为它是基于时间的。

例子：

Order[time=0, quantity=1]
Order[time=1, quantity=2]
Order[time=2, quantity=4]
Order[time=3, quantity=2]

范围和段树：

                sum[0->3=9]
    sum[0->1=3]             sum[2->3=6]
time0=1     time1=2     time2=4     time3=2

如果我添加上面的树会发生什么Order[time=4, quantity=3]

                                        sum[0->4=12]
               sum[0->3=9]                                        sum[4->4=3]
    sum[0->1=3]           sum[2->3=6]                  sum[4->4=3]
time0=1     time1=2   time2=4     time3=2          time4=3

我当然可以使用上面的方法，但我希望有更好的方法。

4

2 回答 2

1

如果您总是在连续的时间值处附加数据，您可以考虑简单地将所有数量的累积总和存储在一个数组中。

您的 1,2,4,2 示例将使数组为 1,3,7,9：

1
1+2=3
1+2+4=7
1+2+4+2=9

然后，您可以通过减去累积数组的两个元素来对一系列元素的值求和。

这是附加的 O(1) 和范围总和的 O(1)。

于 2013-11-04T20:08:36.413 回答
1

我不完全确定我理解你的问题，但听起来你正在寻找一棵Fenwick 树。从数组中，可以在 中构建 Fenwick 树nlog(n)，它们允许在 中的连续范围内求和log(n)，并且您可以在 中更新节点log(n)。我不确定是否要扩展数组；我从未尝试过，但我希望它也会如此log(n)。

于 2013-11-04T20:14:44.147 回答