分段树2 * 2 ^（ceil（log（n））） - 1的数组的内存如何？ [英] How is the memory of the array of segment tree 2 * 2 ^(ceil(log(n))) - 1?

问题描述

链接： http：// www。 geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/ 。这是引用的文本：

The link: http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/. This is the quoted text:

我们从段arr开始[0。 。 。 n-1]。并且每次将当前段划分成两半（如果还没有成为长度为1的段），然后在两半上调用相同的过程，并且对于每个这样的段，我们将和存储在对应的节点中。构建的段树的所有级别将被完全填满，除了最后一级。此外，树将是一个完整的二进制树，因为我们总是在每个级别的两半分割。由于构造的树总是具有n个叶的完整二叉树，所以将存在n-1个内部节点。所以节点的总数将为2n - 1。段树的高度将为[log（n）]。由于使用数组表示树，必须维护父索引和子索引之间的关系，所以为分段树分配的内存大小为2 * 2 ^（ceil（log（n））） - 1。

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 corresponding node. All levels of the constructed segment tree will be completely filled except the last level. Also, the tree will be a Full Binary Tree because we always divide segments in two halves at every level. Since the constructed tree is always full binary tree with n leaves, there will be n-1 internal nodes. So total number of nodes will be 2n – 1. 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 ^(ceil(log(n))) - 1.

如何分配内存（上面的最后一行）多少？如果父代和子索引存储在代码中，如果它是正确的？请在此背后推荐。如果这是错误的，那么什么是正确的值？

How is the memory allocated(last line of the above para) that much? How are the parent and child indexes stored in the code if it is correct? Please give reasoning behind this. If this is false then what is the correct value?

推荐答案

这里发生的是，如果你有一个n个元素，则分段树将为这些n个条目中的每一个具有叶节点。因此，我们有（n）个叶节点和（n-1）个内部节点。

What is happening here is, if you have an array of n elements, then the segment tree will have a leaf node for each of these n entries. Thus, we have (n) leaf nodes, and also (n-1) internal nodes.

节点总数= n +（n-1）= 2n- 1现在，我们知道它是一个完整的二叉树，因此高度是：ceil（Log2（n））+1

Total number of nodes= n + (n-1) = 2n-1 Now, we know its a full binary tree and thus the height is: ceil(Log2(n)) +1

总计数的节点= 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + ... + 2 ^ ceil（Log2（n））//这是一个几何级数，其中2 ^ i表示级别i的节点数。

Total no. of nodes = 2^0 + 2^1 + 2^2 + … + 2^ceil(Log2(n)) // which is a geometric progression where 2^i denotes, the number of nodes at level i.

总和公式GP = a *（r ^ size - 1）/（r-1）
其中a = 2 ^ 0

Formula of summation G.P. = a * (r^size - 1)/(r-1) where a=2^0

总数的节点= 1 *（2 ^（ceil（Log2（n））+ 1）-1）/（2-1）

Total no. of nodes = 1*(2^(ceil(Log2(n))+1) -1)/(2-1)

= 2 * （Log2（n））] -1（数组中的每个内部节点和叶节点都需要空格），因此它是大小的数组。

= 2* [2^ceil(Log2(n))] -1 (you need space in the array for each of the internal as well as leaf nodes which are this count in number), thus it is the array of size.

= O（4 * n）约..

= O(4 * n) approx..

您也可以这样认为，分段树是这样的：

You may also think this way, is the segment tree is this:

    10
   /  \
  3    7
 /\    /\
1  2  3  4

如果上面是段树，那么你的段树数组将是：10， 3,7,1,2,3,4即第0个元素将存储第1个和第2个条目的总和，第1个条目将存储3和4的总和，第2个将存储第5和第6个条目的总和！

If the above is you segment tree, then you array of segment tree will be: 10,3,7,1,2,3,4 i.e. 0th element will store the sum of 1st and 2nd entries, 1st entry will store the sum of 3 and 4th and 2nd will store the sum of 5th and 6th entry!!

另外，更好的解释是：如果数组大小 n 是2的幂，那么我们正好有 n-1 内部节点，总计高达 2n-1 总节点。但并不总是，我们将 n 作为2的幂，所以我们基本上需要 n 的最小功率，这比 n 更大。这意味着这个，

Also, the better explanation is: if the array size n is a power of 2, then we have exactly n-1 internal nodes, summing up to 2n-1 total nodes. But not always, we have n as the power of 2, so we basically need the smallest power of n which is greater then n. That means this,

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

您可能会看到同样的答案 here

You may see my same answer here

这篇关于分段树2 * 2 ^（ceil（log（n））） - 1的数组的内存如何？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！