线段树space要求
Segment tree space requirement
我发现如本文on HackerEarth 所述，线段树可以通过使用数组来实现，其中位于数组索引 n 的节点的子元素是在索引 2n 和 2n+1.
它还指出，为了在我的线段树中存储 n 个元素，我需要 2n+1 个节点。
然而最近当我解决了一些与线段树相关的问题时，有时我的代码会出现运行时错误，当我将存储线段树的数组大小更改为 4 x（数组大小为存储在线段树中）。我如何确定线段树实际上需要 n 个元素的 4n 大小的数组。
2N+1 如果 N 小于 2 的幂（或者如果树是平衡的并且缺少叶子节点都在底行的右侧，类似于文章中的第一个树图）。否则，将节点的索引加倍以获得其子节点将越过数组的边界。查看文章中的中间图（顶部节点中带有“36”的树）。 “16”节点的索引为 6，因此其子节点位于节点 12 和 13。节点“5”没有任何子节点（应该位于节点 10 和 11）。这些缺失的节点仍然需要在阵列中为它们提供插槽。
如果你擅长俄语，请阅读这篇文章：http://e-maxx.ru/algo/segment_tree
如果你不是，我会描述它在说什么：我们需要注意，你包含线段树的数组的大小，使用这样的枚举（左child i 的是 2i，右边的 child 是 2i+1)，将不是 2n，而是 4n。问题是：当 n 不是 2 的幂时，此枚举无法完全正常工作 - 在这种情况下，我们得到 "skipped" 数字，这些数字未分配给任何树顶点（它们意味着 "nodes").实际上，它的工作原理就好像我们将 n 舍入到最接近 2 的幂。它不会使实现更复杂，但会迫使我们将数组的大小增加到 4n。
编辑：这是 above-referenced 文章的 English-version：https://cp-algorithms.com/data_structures/segment_tree.html
我发现如本文on HackerEarth 所述，线段树可以通过使用数组来实现，其中位于数组索引 n 的节点的子元素是在索引 2n 和 2n+1.
它还指出，为了在我的线段树中存储 n 个元素，我需要 2n+1 个节点。
然而最近当我解决了一些与线段树相关的问题时，有时我的代码会出现运行时错误，当我将存储线段树的数组大小更改为 4 x（数组大小为存储在线段树中）。我如何确定线段树实际上需要 n 个元素的 4n 大小的数组。
2N+1 如果 N 小于 2 的幂（或者如果树是平衡的并且缺少叶子节点都在底行的右侧，类似于文章中的第一个树图）。否则，将节点的索引加倍以获得其子节点将越过数组的边界。查看文章中的中间图（顶部节点中带有“36”的树）。 “16”节点的索引为 6，因此其子节点位于节点 12 和 13。节点“5”没有任何子节点（应该位于节点 10 和 11）。这些缺失的节点仍然需要在阵列中为它们提供插槽。
如果你擅长俄语，请阅读这篇文章：http://e-maxx.ru/algo/segment_tree
如果你不是，我会描述它在说什么：我们需要注意，你包含线段树的数组的大小，使用这样的枚举（左child i 的是 2i，右边的 child 是 2i+1)，将不是 2n，而是 4n。问题是：当 n 不是 2 的幂时，此枚举无法完全正常工作 - 在这种情况下，我们得到 "skipped" 数字，这些数字未分配给任何树顶点（它们意味着 "nodes").实际上，它的工作原理就好像我们将 n 舍入到最接近 2 的幂。它不会使实现更复杂，但会迫使我们将数组的大小增加到 4n。
编辑：这是 above-referenced 文章的 English-version：https://cp-algorithms.com/data_structures/segment_tree.html