如本文on HackerEarth 中所述，我发现可以通过使用数组来实现分段树，其中位于数组索引n处的节点的子元素位于索引2n和2n + 1处。
它还指出，要在段树中存储n个元素，我需要2n + 1个节点。
但是最近，当我解决了一些与段树相关的问题时，有时我的代码出现了运行时错误，当我将用于存储段树的数组大小更改为4 x(要存储在段树中的数组大小)时，该错误得到了解决。如何确定分段树实际上需要n个元素的4n大小的数组。
最佳答案
如果您擅长俄语，请阅读此文章: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