段树空间要求

Question

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

它还指出，为了在我的段树中存储n 个元素，我需要2n+1 个节点。

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

Answer 1

如果你擅长俄语，请阅读这篇文章：http : //e-maxx.ru/algo/segment_tree

如果您不是，我将描述它的内容：我们需要注意，包含段树的数组的大小，使用这样的枚举（其中左子节点iis2i和右子节点是2i+1），将不是2n，但是4n。问题是：当n不是 2 的幂时，这个枚举不能完全正常工作——在这种情况下，我们得到“跳过”的数字，这些数字没有分配给任何树顶点（它们的意思是“节点”）。实际上，它就像我们四舍五入n到最接近的 2 次幂一样工作。它不会使实现更复杂，而是迫使我们将数组的大小增加到4n。

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