是否有支持O(1)子序列删除和插入的数据结构

Question

我正在寻找一种优化字符串的方法，以便您可以比Θ(n)更快地删除字符串中的连续段，因为我将执行大量删除操作，并且我的代码有时间限制。

我尝试使用链表，因为您只需更改节点中的"next“变量即可插入或删除段。

虽然这确实会导致O(1)个删除、插入和删除，但我必须首先在Θ(n)时间内遍历链表，到达我想要插入/删除的节点/索引。有没有一个修改过的版本，这样我就不必在每次插入/删除时都遍历链表了？

如果没有这样的东西，我是不是必须构建一个自定义的东西，或者这些要求是不可能的？

Answer 1

一种非常常见的数据结构称为Rope：https://en.wikipedia.org/wiki/Rope_(data_structure)

C++ std::deque是另一个您可以从中获得灵感的应用程序，尽管它可能并不直接适用于其最常见的实现(它可能没有给您足够的控制，并且块大小也不可配置)。

Answer 2

我不认为在O(1)中可以插入和删除子片段。但是，您可以在O(logN)中使用来完成这两项工作。您需要稍微修改一下，并使用隐式treap。

我曾经用这个解决过一个类似的问题。你可以找到我的实现here。如果您想要使用，请根据需要进行更改。