algorithm - 易于移位的分段树

Question

我需要基于段树的数据结构，但与经典段树有一个区别。DS 应该支持元素的轻松移动。我的意思是我想要 ds 我可以：

• l对段进行查询（即从 index到 index的元素总和r）
• 在任何索引之前插入新元素，然后移动新元素右侧的所有元素

如果所有这些操作都可以在O(logn) Greetings中工作，那就太好了

Answer 1

是的，但不确定你能否保持树的平衡。

基本结构是这样的。每个节点只跟踪它跟踪的间隔开始与其子节点之间的分割之间的距离。例如，如果一个节点保持区间 [A, B] 并且有孩子保持 [A,C] 和 [C+1, B] 那么第一个节点应该只存储信息 C - A。这将允许您轻松更改间隔的大小而不必弄乱整个结构。这也意味着当你在里面移动任何东西时，你会使任何现有的迭代器失效，并且每个迭代器都会跟踪间隔。

要执行移位操作：

• 搜索插入点。
• 在路径上选择一个合适的节点。
• 在选定节点上方插入一个新节点。此节点应包含旧 + 新间隔。所以将它的分割值设置为班次的大小。现在新空间是左孩子，旧空间是右孩子。
• 添加您想为新空间保留的任何孩子。
• 更新分割点在左侧的所有父母，因为现在在他们的分割之前有更多的值。

任何其他操作都应该进行相同的操作。您应该选择一个新间隔大致等于节点大小的节点，以便保留 O(logn) 进行操作。显然，一遍又一遍地插入 1 个元素会导致某些路径比其他路径长得多，除非您还添加了一个步骤来重新平衡树。

但是，如果您知道之前的班次，我会简单地向后检查班次并计算所有数据和查询的最终位置 O(N)。然后你可以简单地做一个常规的段树，而不用担心班次。