段树2*2 ^(ceil(log(n))) - 1的数组内存如何？

Question

链接: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)].由于树是使用数组表示的,并且必须维护父索引和子索引之间的关系,因此为分段树分配的内存大小将为2*2 ^(ceil(log(n))) - 1.

如何分配内存(上面的para的最后一行)那么多？如果父代码和子代码索引正确,它们如何存储在代码中？请在此背后给出推理.如果这是假的那么什么是正确的值？

Answer 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的节点数.

求和的公式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个条目的总和,第1个条目将存储总和3和4和2将存储第5和第6个入口的总和!

此外,更好的解释是:如果数组大小n是2的幂,那么我们恰好有n-1个内部节点,总计最多2n-1个节点.但并非总是如此,我们将n作为2的幂,所以我们基本上需要n的最小幂,其大于n.这意味着,

int s=1;
for(; s<n; s<<=1);

你可能会在这里看到我的答案

Answer 2

奇怪的是,当我遇到这个时,我正在阅读与问题相同的来源.我会尽力回答我的问题.

让我们从树表示的基本区别开始(仅在上下文中):

1. 几乎是"最坏情况"的情景.这个并不是完全平衡的,并且在遍历时并不是很有趣.为什么？因为,使用不同的输入,可能会生成不同的树,因此遍历所花费的时间不是很可预测.

2. 我们的"最佳案例"情景.这个是完全平衡或完整的,并且总是会花费可预测的时间来遍历.而且,这棵树也更好"被黑了".

现在让我们回到我们的问题.[请参阅第一张图片]我们知道,对于每个n输入数组(绿色数字),将有n-1个内部节点(蓝色数字).因此,必须分配最多2n-1个节点空间.

但是这里的代码恰恰相反.为什么以及如何？

1. 您的期望:您期望为2n-1节点分配的内存应该足够.换句话说,应该这样做:

   int *st = new int[2*n - 1];
   

   假设其余代码运行良好,这不是一个好主意.那是因为它创造了我们的不平衡树,就像我们的第一种情况一样.这样的树不容易遍历也不容易应用于解决问题.

2. 真正发生的事情:我们添加/填充额外的内存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];
   

   那就是我们分配足够的空间来生成平衡的完整树.这样的树易于遍历(使用一些特殊修改)并且可以直接应用于问题.

我们如何为案例2分配足够的内存？这是如何做:

• 我们知道平衡的Segment Tree中至少有三个组件:

  1. 来自输入数组的n个数字.
  2. 强制要求的n-1个内部节点.
  3. 我们需要为填充分配额外的空间.

• 我们也知道带有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上面的幂,确保我们得到最接近的上限整数:

1. 大于或等于n(输入数组中的元素数).
2. 完美且可重复地被2整除,以获得完全平衡的 2元(二元)树.

Answer 3

设输入数组的大小为 n。
所有输入数组元素都将是段树中的叶节点，因此叶节点数 = n
由于段树是一棵完整的树， 因此段树的高度h = ? 日志₂ n ? + 1
高度为 'h' 的二叉树中的最大节点数为2 ^h -1

那么段树中的节点数 = 2 ^{？日志₂ n ? + 1} -1
等于2*2 ^{？日志₂ n ?} -1

Answer 4

如何确定所需的线段树数组大小？

\n

线段树是满二叉树。但我们用数组来表示它。请记住，在数组表示中表示高度为 h 的任何二叉树，将需要相当于高度为 h 的完美二叉树的空间。

\n

[ Maximum possible Height of a Binary Tree with n nodes] (h) =  Ceil[ Log_2 (n+1) ] - 1 \n[ No. of nodes in a Perfect Binary Tree of height h] (n) = 2 ^ (h+1) - 1\n

\n

给定的数组将代表线段树的叶子。因此，给定数组的大小将是第一个。的叶子。

\n

在线段树中，每对叶子都将由其上一层的父节点连接起来。这些父母将再次与上一级的父母加入。这一直持续到根为止。

\n

例子：

\n

* 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.\n  - Then the total number of nodes in the Binary Tree = No. of interior nodes + No. of leaves. So, 4+3 = 7.\n  - 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 .\n  - 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.\n  - 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.\n  - Thus the Segment Tree Array should also be of the size 7.\n\n* 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.\xc2\xa0\n  - Then the total number of nodes in the Binary Tree = No. of interior nodes + No. of leaves. So, 5+4 = 9.\n  - 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 .\n  - 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.\n  - 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.\n  - Thus the Segment Tree Array should also be of the size 15.\n

\n

一般来说，

\n

* 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. \n  - Then the total number of nodes in the Binary Tree = No. of interior nodes + No. of leaves. So, 2N-1.\n  - 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 .\n  - 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.\n  - 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.\n  - Thus the Segment Tree Array should also be of the size 2 ^ (Ceil[ Log_2 (2N) ] ) - 1.\n  - This can also be written as [2*2 ^ (Ceil[ Log_2 (N) ] )] - 1.\n

\n

因此，线段树数组的大小 = [2*2 ^ (Ceil[ Log_2 (N) ] )] - 1

\n

线段树数组的大小仅为 4N（大约）。

\n

例子：

\n

Best Case Scenario: (No. of leaves (N) is a power of 2)\nSay, the no. of leaves , N is 4. \nSince N is a power of 2, the Segment tree will be a Perfect Binary Tree.\nSo the total no of nodes will be N+N-1 = 2N-1 = 7\nSo, the size of the Segment Tree Array = 7.\n\nNot the Best Case Scenario: (No. of leaves  (N) is not a power of 2)\nIf the no. of leaves , N is 5. \nSince 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. \nWe 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.\nNow, total no. of nodes in the segment tree upto the previous power of 2. i.e. 8 is 8+7 = 15\nSo, the no. of nodes in the new level will be 15+1 = 16\nSo, the size of the Segment Tree Array = 15 + 16 = 31.\n

\n

一般来说，

\n

Best Case Scenario: (No. of leaves (N) is a power of 2)\nSince N is a power of 2, the Segment tree will be a Perfect Binary Tree.\nSo the total no of nodes will be N+N-1 = 2N-1\nSo, the size of the Segment Tree Array = 2N-1\n\nNot the Best Case Scenario: (No. of leaves  (N) is not a power of 2)\nSince 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. \nWe 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.\nNow, total no. of nodes in the segment tree upto the previous power of 2 will be 2N-1.\nSo, the no. of nodes in the new level will be 2N-1+1 = 2N\nSo, the size of the Segment Tree Array = 2N + 2N - 1 = 4N - 1 = 4N (approx.)\n

\n

因此，线段树数组的大小 = 4N（大约）

\n