线段树内存管理

Question

我见过很多使用O(4*N)内存的线段树实现。是否有办法让线段树只使用恰好2*N-1的内存？我找不到任何这样的实现。即使它们谈论空间复杂度实际上是2*N-1，它们仍然分配4*N的内存。

编辑：我的意思是对于一个包含n个数字的数组，您可以使用一个包含2n-1个数字的数组来构建线段树。每个实现都使用一个包含2 *（大于n的下一个2的幂）的数组。

我知道O符号省略常数，但对于非常大的n，2*N-1和4*N之间的差别很重要，这就是我提出这个问题的原因。

- Andrew

Answer 1

根据大O符号，O(4*N) = O(2*N-1) = O(N)。任何标准的线段树实现都使用线性内存。

针对你的问题，考虑一个数组a[0...n-1]作为输入。假设n = 10。当你构建线段树时，它将类似于以下内容：

构建所需节点数= 2*n-1 = 19。因此，理论上仅需要19个节点！

但是，我们使用数组数据结构实现线段树。在这里，每个节点将对应于array中的某个索引。在线段树中，对于索引为x的节点，左子索引=2*x，右子索引=2*x+1。

因此，如果我从一个以1为基数的数组开始，[0,9]的索引=1，[5]的索引=24，[6]的索引=25。因此，在这种情况下，您至少需要索引到25。在最坏的情况下，在完全成长的线段树(n=16)中，您将需要31的索引。

因此，我们使用大小为2*(next power of 2 >= n)的array来维护它。

- Rishit Sanmukhani

Answer 2

O(4N) = O(2N) = O(N)，因为O-notation从常数因子中抽象出来。

wikipedia Big O notation

那么你所说的“使用恰好2N-1内存”是什么意思？你是指2N-1字节吗？如果你的意思是O(2N-1)，那么这与O(4N)，O(2*N)和O(N)相同。

- MrSmith42

Answer 3

您可以动态地向树中添加节点。那么您没有使用的节点将不会存在，也不会浪费内存。

- noobgotbanned

Answer 4

大多数人都熟悉实现安全的4N分配内存，这恰好是构建大小为N的数组上的段树或面向对象编程版本的上限。关于此背后的一些想法，请阅读这里。这是一个非常好的资源，包含了很多关于段树的信息。

现在，让我们来看看2N的内存使用情况。请参考这里，这里以及：

内存高效实现（来自这里）

大多数人使用上一节的实现。如果您查看数组t，可以看到它按照BFS遍历（层序遍历）的顺序遵循树节点的编号。使用此遍历，顶点v的子节点分别为2v和2v+1。但是，如果n不是2的幂，则此方法将跳过某些索引并留下数组t未使用的部分。尽管一个由n个元素组成的线段树仅需要2n-1个顶点，但内存消耗受4n限制。 然而，这可以被减少。我们按照欧拉遍历（先序遍历）的顺序重新编号树的顶点，并将所有这些顶点写在一起。

让我们看一下索引为v的顶点，让他负责[l,r]这个区间，令mid=l+r2。显然，左子节点的索引将是v+1。左子节点负责[mid,l]这个区间，在左子树中总共会有2∗(mid−l+1)−1个顶点。因此，我们可以计算出v的右子节点的索引。该索引将是v+2∗(mid−l+1)。通过这种编号方式，我们实现了将所需内存减少到2n的目的。

- Arrow