链接：http ://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/ 。这是引用的文字：
我们从段 arr[0 开始。. . n-1]。并且每次我们将当前段分成两半（如果它还没有变成长度为 1 的段），然后在两半上调用相同的过程，并且对于每个这样的段，我们将总和存储在相应的节点中。除最后一层外，构建的段树的所有层都将被填充。此外，这棵树将是一个完整的二叉树，因为我们总是在每一层将段分成两半。由于构建的树始终是具有 n 个叶子的完整二叉树，因此将有 n-1 个内部节点。所以节点的总数将是 2n – 1。段树的高度将是 ceil[log(n)]。由于树是使用数组表示的，并且必须维护父索引和子索引之间的关系，因此为段树分配的内存大小将为
.
这么多内存是如何分配的（上段的最后一行）？如果正确，父子索引如何存储在代码中？请给出这背后的原因。如果这是错误的，那么正确的值是多少？
这里发生的情况是，如果您有一个包含 n 个元素的数组，那么段树将为这 n 个条目中的每一个条目提供一个叶节点。因此，我们有 (n) 个叶节点，以及 (n-1) 个内部节点。
节点总数= n + (n-1) = 2n-1 现在，我们知道它是一棵完整的二叉树，因此高度为：ceil(Log2(n)) +1
总数 of nodes = 2^0 + 2^1 + 2^2 + … + 2^ceil(Log2(n)) // 这是一个几何级数，其中 2^i 表示第 i 层的节点数。
求和公式 GP = a * (r^size - 1)/(r-1) 其中 a=2^0
总数 节点数 = 1*(2^(ceil(Log2(n))+1) -1)/(2-1)
= 2* [2^ceil(Log2(n))] -1 （每个内部节点和叶节点都需要数组中的空间，这些节点是这个数量的），因此它是大小数组。
= O(4 * n) 大约..
你也可以这样想，让下面是段树：
10
/ \
3 7
/\ /\
1 2 3 4
如果上面是您的分段树，那么您的分段树数组将是：10,3,7,1,2,3,4 即第 0 个元素将存储第 1 个和第 2 个条目的总和，第一个条目将存储第 3 和第 4 和第 2 将存储第 5 和第 6 项的总和！
此外，更好的解释是：如果数组大小n是 2 的幂，那么我们正好有n-1 个内部节点，总节点数为2n-1。但并非总是如此，我们有n作为 2 的幂，所以我们基本上需要大于n的2的最小幂。这意味着，
int s=1;
for(; s<n; s<<=1);
你可能会在这里看到我同样的答案
奇怪的是，当我遇到这个问题时，我正在阅读与问题相同的来源。我会尽力回答我的。
让我们从树表示的基本区别开始（仅在上下文中）：
几乎是“最坏情况”的情况。这个不是完全平衡的，遍历也不是很有趣。为什么？因为，使用不同的输入，可能会生成不同的树，因此遍历所花费的时间不是很可预测的。
我们的“最佳案例”场景。这个是完全平衡的或完整的，并且总是需要可预测的时间来遍历。而且，这棵树也比较好“砍”。
现在让我们回到我们的问题。[参考第一张图] 我们知道，对于每个n 输入数组（绿色数字），都会有n-1 个内部节点（蓝色数字）。所以最多必须分配2n-1 个节点空间。
但是这里的代码恰恰相反。为什么以及如何？
您的期望：您期望分配给2n-1个节点的内存应该足够了。换句话说，应该这样做：
int *st = new int[2*n - 1];
假设其余代码运行良好，这不是一个好主意。那是因为它创建了我们的不平衡树，就像我们的第一种情况一样。这样的树不容易遍历，也不容易应用于解决问题。
真正发生了什么：null我们用or0值添加/填充额外的内存。我们这样做：
int x = (int)(ceil(log2(n))); //Height of segment tree
int max_size = 2*(int)pow(2, x) - 1; //Maximum size of segment tree
int *st = new int[max_size];
那就是我们分配足够的空间来生成平衡的完整树。这样的树很容易遍历（使用一些特殊的修改）并且可以直接应用于问题。
我们如何为案例 2分配足够的内存？就是这样：
我们知道我们的平衡段树中至少有三个组件：
我们还知道具有k个叶子的平衡树将具有：
将两者结合起来，我们得到了预期的结果：
int x = (int)(ceil(log2(n))); //Height of segment tree
int max_size = 2*(int)pow(2, x) - 1; //Maximum size of segment tree
int *st = new int[max_size];
琐事！将 2 提高到上面的幂x，确保我们得到最接近的上限整数，即：
n（我们输入数组中的元素数）。设输入数组的大小为 n。
所有的输入数组元素都是segment tree中的叶子节点所以叶子节点的数量=n
由于segment tree是一棵完整的树 所以segment Tree的Hight =⌈Log 2n⌉ + 1
二进制的最大节点数高度“h”的树是2 h -1
所以段树中的节点数 = 2 ⌈ Log 2 n ⌉ + 1 -1
等于2*2 ⌈ Log 2 n ⌉ -1
段树是完全二叉树。但是我们在一个数组中表示它。请记住，在数组表示中表示任何高度为 h 的二叉树，将需要与高度为 h 的完美二叉树等效的空间。
[ Maximum possible Height of a Binary Tree with n nodes] (h) = Ceil[ Log_2 (n+1) ] - 1
[ No. of nodes in a Perfect Binary Tree of height h] (n) = 2 ^ (h+1) - 1
给定的数组将代表线段树的叶子。因此，给定数组的大小将是第一个。叶子。
在分段树中，每对叶子都将由其上一层的父节点连接。这些父母将再次与他们的父母在上一级加入。这种情况一直持续到根。
* Say, if there are 4 leaves in a Binary Tree, then the maximum no. of interior nodes in the Binary Tree will be N-1. So, 3.
- Then the total number of nodes in the Binary Tree = No. of interior nodes + No. of leaves. So, 4+3 = 7.
- The max possible height of this Binary Tree will be 2. Formula: Maximum possible Height of a Binary Tree (h) = Ceil[ Log_2 (n+1) ] - 1 .
- Remember, the total space required in the Segment Tree Array will be nothing but the total no. of nodes of the Perfect Binary Tree at this height.
- So, the total no. of nodes of the Perfect Binary Tree at this height is (n) = 7. Formula: No. of nodes in a Perfect Binary Tree (n) = 2 ^ (h+1) - 1.
- Thus the Segment Tree Array should also be of the size 7.
* But if there is one more leaf, say 5 and remember that this leaf can be anywhere between the beginning of the level till the end of the level.
- Then the total number of nodes in the Binary Tree = No. of interior nodes + No. of leaves. So, 5+4 = 9.
- The max possible height of this Binary Tree will be 3. Maximum possible Height of a Binary Tree (h) = Ceil[ Log_2 (n+1) ] - 1 .
- Remember, the total space required in the Segment Tree Array will be nothing but the total no. of nodes of the Perfect Binary Tree at this height.
- So, the total no. of nodes of the Perfect Binary Tree at this height is (n) = 15. Formula: No. of nodes in a Perfect Binary Tree (n) = 2 ^ (h+1) - 1.
- Thus the Segment Tree Array should also be of the size 15.
一般来讲，
* Say, if there are N leaves in a Binary Tree, then the maximum no. of interior nodes in the Binary Tree will be N-1.
- Then the total number of nodes in the Binary Tree = No. of interior nodes + No. of leaves. So, 2N-1.
- The max possible height of this Binary Tree will be Ceil[ Log_2 (2N) ] - 1. Formula: Maximum possible Height of a Binary Tree (h) = Ceil[ Log_2 (n+1) ] - 1 .
- Remember, the total space required in the Segment Tree Array will be nothing but the total no. of nodes of the Perfect Binary Tree at this height.
- So, the total no. of nodes of the Perfect Binary Tree at this height is (n) = 2 ^ (Ceil[ Log_2 (2N) ] ) - 1. Formula: No. of nodes in a Perfect Binary Tree (n) = 2 ^ (h+1) - 1.
- Thus the Segment Tree Array should also be of the size 2 ^ (Ceil[ Log_2 (2N) ] ) - 1.
- This can also be written as [2*2 ^ (Ceil[ Log_2 (N) ] )] - 1.
因此，Segment Tree Array 的大小 = [2*2 ^ (Ceil[ Log_2 (N) ] )] - 1
Best Case Scenario: (No. of leaves (N) is a power of 2)
Say, the no. of leaves , N is 4.
Since N is a power of 2, the Segment tree will be a Perfect Binary Tree.
So the total no of nodes will be N+N-1 = 2N-1 = 7
So, the size of the Segment Tree Array = 7.
Not the Best Case Scenario: (No. of leaves (N) is not a power of 2)
If the no. of leaves , N is 5.
Since N is not a power of 2, the Segment Tree will need one more entire level to accommodate the extra 1 leaf, as this leaf can be anywhere from the beginning of the level till the end.
We know that in a Perfect binary tree, the no of nodes in every new level, will be equal to No. of all the previous level nodes + 1.
Now, total no. of nodes in the segment tree upto the previous power of 2. i.e. 8 is 8+7 = 15
So, the no. of nodes in the new level will be 15+1 = 16
So, the size of the Segment Tree Array = 15 + 16 = 31.
一般来讲，
Best Case Scenario: (No. of leaves (N) is a power of 2)
Since N is a power of 2, the Segment tree will be a Perfect Binary Tree.
So the total no of nodes will be N+N-1 = 2N-1
So, the size of the Segment Tree Array = 2N-1
Not the Best Case Scenario: (No. of leaves (N) is not a power of 2)
Since N is not a power of 2, the Segment Tree will need one more entire level to accommodate the extra leaves, as this leaf can be anywhere from the beginning of the level till the end.
We know that in a Perfect binary tree, the no of nodes in every new level, will be equal to No. of all the previous level nodes + 1.
Now, total no. of nodes in the segment tree upto the previous power of 2 will be 2N-1.
So, the no. of nodes in the new level will be 2N-1+1 = 2N
So, the size of the Segment Tree Array = 2N + 2N - 1 = 4N - 1 = 4N (approx.)
因此，Segment Tree Array 的大小 = 4N（大约）
段树将是一个完整的二叉树，其中所有叶子都表示输入数组中的元素。正如这里提到的
完整二叉树中的节点数n至少为n = 2h+1且最多 为 n = 2^{h+1} - 1，其中h是树的高度。并且h = log_2n。
Note - log_2n indicates log base 2
这是用于找出段树中最大节点数的python代码 -
from math import pow, log, ceil
def initialize_seg_tree(input_arr):
n = len(input_arr)
height = ceil(log(n, 2))
# max_nodes = 2^(h+1) - 1, where h = log(n) // base 2
seg_tree_size = int(pow(2, height + 1) - 1)
seg_tree_arr = empty_1d_array(seg_tree_size)
return seg_tree_arr
这里有一些链接 .. 从 n（任意数量）长度的数组构建大小为 2*n-1 的段树的迭代实现https://www.geeksforgeeks.org/segment-tree-efficient-implementation/ 用于构建的递归实现从 n（任意数字）长度的数组中分割大小为 2*n-1 的树https://www.hackerearth.com/practice/notes/segment-tree-and-lazy-propagation/#c191521
从 n（任意数字）的数组构建大小小于 4*n 的段树的迭代实现https://codeforces.com/blog/entry/18051