algorithm - 设计一个数据结构

Question

我正在尝试设计一种数据结构，它根据一些规定的顺序存储元素，每个元素都有自己的值，并且支持以下各项对数时间的四个操作(摊销或最坏情况，您的选择):

1. 在第k个位置添加一个值为v的新元素
2. 删除第k个元素
3. 返回元素 i 到 j 的值之和
4. 将元素 i 到 j 的值增加 x

任何想法将不胜感激，谢谢

Answer 1

我怀疑你可以用红黑树来做。在经典的红黑树上，每个节点都需要以下附加字段:

• 大小
• 总结
• 增加

size 字段将跟踪子节点的总数，允许 log(n) 次插入和删除。

sum 字段将跟踪其子节点的总和，允许 log(n) 时间求和。

增量字段将用于跟踪其每个子节点的增量，这些子节点将在计算总和时添加。因此，在计算最终总和时，我们将返回 sum + size*increment。这是最棘手的一个。计算总和时将添加增量字段。我认为通过在适当的节点添加正增量和负增量，可以在所有情况下通过仅更改 log(n) 节点来正确更改返回的总和。

不用说，实现起来会非常棘手。 Sum 和 increment 字段必须在每次插入和删除后更新，并且每个字段至少有五种情况需要处理。

更新:我不打算尝试完全解决这个问题，但我会注意到将 i 递增到 j 相当于将整棵树递增 n，然后将 0 递减到 i 递增 n，将 j 递减到结束于 n。全局递增可以在常数时间内完成，另外两个操作是“左侧递减”和“右侧递减”，它们是对称的。对 i 进行左侧递减类似于“获取根节点的左子树的计数”。如果计数小于 i，则将 root 的左子节点的增量字段减 n。然后将 n 的左递减应用于根节点的右子树，直到 i - count(left subtree) 个元素。或者，如果计数大于 i，则将根的左-左孙子的增量字段递减 n，然后将 n 的左递减应用于根的左右子树，直到计数(左-左子树)'。由于树是平衡的，我认为左减操作只需要递归应用 ln(n) 次。右减量与此类似，但相反。