Fenwick树和段树在C++中能以对数时间执行插入和删除操作吗?

huangapple go评论68阅读模式
英文:

Can Fenwick Tree and Segment Tree in C++ perform insertions and deletions in logarithmic time?

问题

我提前为可能是一个非常愚蠢的问题而道歉。最近我一直在阅读关于 Fenwick 树和线段树的内容
(线段树的具体实现在这里: https://cp-algorithms.com/data_structures/segment_tree.html#implementation)
(Fenwick 树的示例在这里: https://cp-algorithms.com/data_structures/fenwick.html)

但尽管我进行了所有这些阅读,似乎没有任何来源提到插入和删除树中元素的时间复杂性 --- 只有查询和更新(这两者都需要 log(n) 时间)。
我是否正确地认为 Fenwick 树和线段树的插入和删除元素不能在 log(n) 时间内完成?

英文:

I apologize in advance for what may be a really dumb question. I've been reading about fenwick tree and segment tree a lot recently
(specific implementation of segment tree is here: https://cp-algorithms.com/data_structures/segment_tree.html#implementation)
(fenwick tree example here: https://cp-algorithms.com/data_structures/fenwick.html)

But despite all my readings none of the sources seemed to talk about the time complexity for inserting and deleting an element from the tree --- only querying and updating (both takes log(n)).
Am I correct in assuming that inserting and deleting an element for fenwick tree and segment tree can't be done in logn time?

答案1

得分: 1

Fenwick Trees 和 Segment Trees 只适用于固定大小的数组。
无法在不重新计算树中大量预计算数据的情况下插入新元素。无法在对数时间内插入新值。

然而,如果你使用一个小技巧,删除是有可能的:你可以将元素更新为中性值。
例如,如果你使用这些数据结构来计算总和,那么你可以通过将其值更新为 0 来删除一个元素。
如果你使用数据结构来计算最大值,那么将元素替换为负无穷大。

如果你需要一个数据结构,允许在对数时间内执行典型的查询和更新操作,而且还可以在对数时间内插入和删除,请查看Treap数据结构。

英文:

Both Fenwick Trees and Segment Trees only work over an array of a fixed size.
It's not possible to insert new elements without recomputing a large amount of the precomputed data in the tree. It's not possible to insert a new value in logarithmic time.

Deleting however is somewhat possible if you apply a trick: you can update the element with a neutral value.
E.g. if you use the data structures in order to compute sums, then you could delete an element by updating it's value to 0.
If you use the data structure to compute maxima, then replace the element with negative infinity.


If you need a data structure that allows the typical operations like query and update in logarithmic time, and additionally inserts and deletes in logarithmic time, you can take a look at the Treap data structure.

huangapple
  • 本文由 发表于 2023年5月25日 15:00:01
  • 转载请务必保留本文链接:https://go.coder-hub.com/76329633.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定