线段树2 * 2 ^(ceil(log(n))) - 1的数组内存如何？
How is the memory of the array of segment tree 2 * 2 ^(ceil(log(n))) - 1?
link：http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/。这是引用的文字：
We start with a segment arr[0 . . . n-1]. And every time we divide the current segment into two halves(if it has not yet become a segment of length 1), and then call the same procedure on both halves, and for each such segment, we store the sum in the corresponding node. All levels of the constructed segment tree will be filled except the last level. Also, the tree will be a Full Binary Tree because we always divide segments into two halves at every level. Since the constructed tree is always a full binary tree with n leaves, there will be n-1 internal nodes. So the total number of nodes will be 2n – 1. The height of the segment tree will be ceil[log(n)]. Since the tree is represented using array and relation between parent and child indexes must be maintained, size of memory allocated for segment tree will be
 "\(2 * 2^{\left\lceil\log _{2} n\right\rceil}-1\)")
.
那么多内存是怎么分配的（上段最后一行）？如果正确的话，父子索引如何存储在代码中？请给出这背后的原因。如果这是错误的，那么正确的值是多少？
这里发生的事情是，如果你有一个包含 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 层的节点数。
求和公式G.P。 = a * (r^size - 1)/(r-1)
其中 a=2^0
总人数节点数 = 1*(2^(ceil(Log2(n))+1) -1)/(2-1)
= 2* [2^ceil(Log2(n))] -1（数组中的每个内部节点和叶节点都需要 space，这是数量），因此它是大小的数组。
= O(4 * n) 约..
你也可以这么想，下面就是线段树：
10
/ \
3 7
/\ /\
1 2 3 4
如果上面是你的线段树，那么你的线段树数组将是：10,3,7,1,2,3,4 即第 0 个元素将存储第 1 个和第 2 个条目的总和，第 1 个条目将存储第 3 项和第 4 项的总和，第 2 项将存储第 5 项和第 6 项的总和！
此外，更好的解释是：如果数组大小 n 是 2 的幂，那么我们正好有 n-1内部节点，总共 2n-1 个节点。但并非总是如此，我们有n作为2的次方，所以我们基本上需要2的最小次方大于n。也就是说，
int s=1;
for(; s<n; s<<=1);
你可能会看到我相同的答案here
奇怪的是，当我遇到这个问题时，我正在阅读与问题相同的来源。我会尽力回答。
让我们从树表示的基本差异开始（仅在 context 中）：
差不多"Worst Case"的场景。这一个 不完全平衡 并且遍历起来不是很有趣。为什么？因为，使用不同的输入，可能会生成不同的树，因此遍历所花费的时间不是很可预测。
我们的 "Best Case" 场景。这一个 完全平衡或完整 并且总是需要可预测的时间来遍历。而且，这棵树也比较好"hacked"。
现在让我们回到我们的问题。 [参考第一张图]我们知道对于每个n-input数组（green中的数字），都会有n-1个内部节点（blue中的数字）。所以最多必须分配2n-1个节点space。
但是代码 here 做了相反的事情。为什么以及如何？
您的期望： 您期望分配给 2n-1 个节点的内存应该足够。换句话说，应该这样做：
int *st = new int[2*n - 1];
假设其余代码运行良好，这不是一个好主意。那是因为它创建了我们的不平衡树，很像我们的第一个例子。这样的树不好遍历也不好应用到解题中
真正发生的事情： 我们 add/pad 额外的内存 null 或 0 值。我们这样做：
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];
也就是说我们分配了足够的space来生成一个平衡的完全树。这样的树很容易遍历（使用一些特殊的修改），可以直接应用于问题。
我们如何为 案例 2 分配足够的内存？方法如下：
我们知道在我们的平衡线段树中至少有三个组成部分：
- n 来自我们输入数组的数字。
- n-1个强制要求的内部节点。
- 我们需要为 padding.
分配额外的 space
我们还知道，具有 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（输入数组中的元素数）。
- 被2完美重复整除，得到一棵完全平衡 二元（二叉）树。
令输入数组的大小为n。
所有输入数组元素都是线段树中的叶节点，因此 叶节点数 = n
由于Segment tree是一个complete tree 所以Segment Tree的Hight h = ⌈ Log2n ⌉ + 1
高度为“h”的二叉树中的最大节点数为2h-1
So 一个线段树的节点数 = 2⌈ Log2n ⌉ + 1 -1
等于 2*2⌈ Log2n ⌉ -1
线段树将是一棵全二叉树，其中所有叶子都表示输入数组中的元素。如前所述 here
The number of nodes n in a full binary tree, is at
least n = 2h+1 and at most
n = 2^{h+1} - 1, where h is
the height of the tree. And 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（任意数字）https://www.geeksforgeeks.org/segment-tree-efficient-implementation/ 的数组构建大小为 2*n-1 的线段树的迭代实现
从长度为 n（任意数字）https://www.hackerearth.com/practice/notes/segment-tree-and-lazy-propagation/#c191521
的数组构建大小为 2*n-1 的线段树的递归实现
从 n（任意数字）的数组构建大小小于 4*n 的线段树的迭代实现 https://codeforces.com/blog/entry/18051
如何确定所需的线段树数组大小？
线段树是一棵满二叉树。但是我们在一个数组中表示它。请记住，在数组表示中表示任何高度为 h 的二叉树，将需要 space 等同于高度为 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
给定的数组将代表线段树的叶子。因此，给定数组的大小将是编号。叶子。
在一个线段树中，每一对叶子都将由它们在前一层的 parent 连接起来。这些 parent 将再次与它们在上一级的 parent 连接。这一直持续到根。
示例：
* 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.
因此，线段树数组的大小=[2*2^(Ceil[Log_2(N)])] - 1
线段树数组的大小仅为4N（约）。
示例：
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.)
因此，线段树数组的大小= 4N（约）
link：http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/。这是引用的文字：
We start with a segment arr[0 . . . n-1]. And every time we divide the current segment into two halves(if it has not yet become a segment of length 1), and then call the same procedure on both halves, and for each such segment, we store the sum in the corresponding node. All levels of the constructed segment tree will be filled except the last level. Also, the tree will be a Full Binary Tree because we always divide segments into two halves at every level. Since the constructed tree is always a full binary tree with n leaves, there will be n-1 internal nodes. So the total number of nodes will be 2n – 1. The height of the segment tree will be ceil[log(n)]. Since the tree is represented using array and relation between parent and child indexes must be maintained, size of memory allocated for segment tree will be
那么多内存是怎么分配的（上段最后一行）？如果正确的话，父子索引如何存储在代码中？请给出这背后的原因。如果这是错误的，那么正确的值是多少？
这里发生的事情是，如果你有一个包含 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 层的节点数。
求和公式G.P。 = a * (r^size - 1)/(r-1) 其中 a=2^0
总人数节点数 = 1*(2^(ceil(Log2(n))+1) -1)/(2-1)
= 2* [2^ceil(Log2(n))] -1（数组中的每个内部节点和叶节点都需要 space，这是数量），因此它是大小的数组。
= O(4 * n) 约..
你也可以这么想，下面就是线段树：
10
/ \
3 7
/\ /\
1 2 3 4
如果上面是你的线段树，那么你的线段树数组将是：10,3,7,1,2,3,4 即第 0 个元素将存储第 1 个和第 2 个条目的总和，第 1 个条目将存储第 3 项和第 4 项的总和，第 2 项将存储第 5 项和第 6 项的总和！
此外，更好的解释是：如果数组大小 n 是 2 的幂，那么我们正好有 n-1内部节点，总共 2n-1 个节点。但并非总是如此，我们有n作为2的次方，所以我们基本上需要2的最小次方大于n。也就是说，
int s=1;
for(; s<n; s<<=1);
你可能会看到我相同的答案here
奇怪的是，当我遇到这个问题时，我正在阅读与问题相同的来源。我会尽力回答。
让我们从树表示的基本差异开始（仅在 context 中）：
差不多"Worst Case"的场景。这一个 不完全平衡 并且遍历起来不是很有趣。为什么？因为，使用不同的输入，可能会生成不同的树，因此遍历所花费的时间不是很可预测。
我们的 "Best Case" 场景。这一个 完全平衡或完整 并且总是需要可预测的时间来遍历。而且，这棵树也比较好"hacked"。
现在让我们回到我们的问题。 [参考第一张图]我们知道对于每个n-input数组（green中的数字），都会有n-1个内部节点（blue中的数字）。所以最多必须分配2n-1个节点space。
但是代码 here 做了相反的事情。为什么以及如何？
您的期望： 您期望分配给 2n-1 个节点的内存应该足够。换句话说，应该这样做：
int *st = new int[2*n - 1];假设其余代码运行良好，这不是一个好主意。那是因为它创建了我们的不平衡树，很像我们的第一个例子。这样的树不好遍历也不好应用到解题中
真正发生的事情： 我们 add/pad 额外的内存
null或0值。我们这样做：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];也就是说我们分配了足够的space来生成一个平衡的完全树。这样的树很容易遍历（使用一些特殊的修改），可以直接应用于问题。
我们如何为 案例 2 分配足够的内存？方法如下：
我们知道在我们的平衡线段树中至少有三个组成部分：
- n 来自我们输入数组的数字。
- n-1个强制要求的内部节点。
- 我们需要为 padding. 分配额外的 space
我们还知道，具有 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（输入数组中的元素数）。 - 被2完美重复整除，得到一棵完全平衡 二元（二叉）树。
令输入数组的大小为n。
所有输入数组元素都是线段树中的叶节点，因此 叶节点数 = n
由于Segment tree是一个complete tree 所以Segment Tree的Hight h = ⌈ Log2n ⌉ + 1
高度为“h”的二叉树中的最大节点数为2h-1
So 一个线段树的节点数 = 2⌈ Log2n ⌉ + 1 -1
等于 2*2⌈ Log2n ⌉ -1
线段树将是一棵全二叉树，其中所有叶子都表示输入数组中的元素。如前所述 here
The number of nodes n in a full binary tree, is at least n = 2h+1 and at most n = 2^{h+1} - 1, where h is the height of the tree. And 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（任意数字）https://www.geeksforgeeks.org/segment-tree-efficient-implementation/ 的数组构建大小为 2*n-1 的线段树的迭代实现 从长度为 n（任意数字）https://www.hackerearth.com/practice/notes/segment-tree-and-lazy-propagation/#c191521
的数组构建大小为 2*n-1 的线段树的递归实现从 n（任意数字）的数组构建大小小于 4*n 的线段树的迭代实现 https://codeforces.com/blog/entry/18051
如何确定所需的线段树数组大小？
线段树是一棵满二叉树。但是我们在一个数组中表示它。请记住，在数组表示中表示任何高度为 h 的二叉树，将需要 space 等同于高度为 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
给定的数组将代表线段树的叶子。因此，给定数组的大小将是编号。叶子。
在一个线段树中，每一对叶子都将由它们在前一层的 parent 连接起来。这些 parent 将再次与它们在上一级的 parent 连接。这一直持续到根。
示例：
* 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.
因此，线段树数组的大小=[2*2^(Ceil[Log_2(N)])] - 1
线段树数组的大小仅为4N（约）。
示例：
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.)
因此，线段树数组的大小= 4N（约）