线段树空间要求

Question

我在这篇HackerEarth的文章中发现，可以使用数组来实现分段树。对于位于数组索引为n的节点的子元素，在索引2n和2n+1的位置上。

此外，文章指出，要将n个元素存储在分段树中，需要2n+1个节点。

然而，最近当我解决与分段树相关的问题时，有时我的代码会出现运行时错误，当我将用于存储分段树的数组大小更改为4 x (要存储在分段树中的数组的大小)时，该错误得到了解决。我如何确保分段树实际上需要4n大小的数组来存储n个元素？

- brijs

---

请注意，左子树（N）= 2N; 右子树(N) = 2N+1 这种方式适用于简单的二叉树，但仅当从 N=1 开始时才有效，而不是从 N=0 开始。您可以修正它，使其从 N=0 开始有效，但这需要使用略有不同的公式（LC(N) = 2N+1; RC(N)=2N+2）。我不清楚为什么您需要 2N+1 个节点来存储具有 N 个条目的树；如果您可以分配索引从 1 开始的第一个元素，那么 N 就足够了，如果您分配从 0 开始，但只使用从 1 开始的元素，则需要 N+1。两者都不会膨胀两倍。_ […继续…]_ - Jonathan Leffler

文章中可能有原因——它正在存储范围，如果每个范围占用两个单元格，那么您需要加倍；但是文章很长，您的问题并不适合在SO上提问。您应该展示为什么需要使用4N的一些代码，然后我们可以验证它。或者其他什么的。 - Jonathan Leffler

这适合发布在其他的 StackExchange 论坛吗？ - brijs

不确定，我不经常访问其他Stack Exchange网站。你可以看看Programmers，但我不确定他们是否会同意。我认为还有一个计算机科学网站；同上 - 但我在所有网站列表中找不到它。您可以通过展示实现4N内容的代码并检查是否需要来拯救SO的问题。我更仔细地查看了这篇文章，似乎比我预期的多了一层节点（对于N = 7，它有一堆节点，需要大约13个节点; 我还没有弄清楚原因）。 - Jonathan Leffler

在进一步搜索后，我找到了这个链接，但是无法理解它，是否有更简单的解释：https://www.quora.com/Why-does-4-%2A-N-space-have-to-be-allocated-for-a-segment-tree-where-N-is-the-size-of-the-original-array/answer/Brian-Bi?srid=iHMe - brijs

https://discuss.codechef.com/questions/85040/size-of-segment-tree - Rohith R

Answer 1

如果您擅长俄语，请阅读这篇文章：http://e-maxx.ru/algo/segment_tree 如果不是，我来描述一下它在说什么：我们需要注意的是，将线段树存储在数组中时，使用这种枚举方式（其中节点i的左子树为2i，右子树为2i+1），数组的大小不会是2n，而是4n。问题在于：当n不是2的幂时，这种枚举方式并不能完全正常地工作 - 在这种情况下，我们会得到“跳过”的数字，它们没有被分配给任何树节点。实际上，它的工作方式就好像我们将n向上取整到最接近2的幂。这并不会使实现更加复杂，但强制我们将数组的大小增加到4n。

编辑：这里是上面提到的文章的英文版：https://cp-algorithms.com/data_structures/segment_tree.html

- RedRidingHood

Answer 2

如果N比2的次方少1（或者树是平衡的，缺失的叶子节点都在底部行的右侧，类似于文章中的第一棵树形图），那么2N+1个节点将按照给定方式定位其子节点。 否则，将一个节点的索引加倍以获取其子节点将超出数组的边界。查看文章中的中间图表（顶部节点为“36”的树）。 “16”节点的索引为6，因此其子节点将位于节点12和13。 节点“5”没有任何子节点（它们应该在节点10和11中）。 这些缺失的节点仍然需要在数组中为它们保留空间。

- 1201ProgramAlarm