线段树数组的内存是多少？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）]。 由于使用数组表示树并且必须维护父对象和子对象索引之间的关系，因此为线段树分配的内存大小将是 。

如何分配这么多内存（上述段落的最后一行）？ 如果它是正确的，父对象和子对象索引是如何存储在代码中的？ 请解释其中的原因。 如果这是错误的，则正确值是多少？

- dauntless

Answer 1

如果您有一个包含n个元素的数组，那么线段树将为每个这些n个条目创建一个叶节点。因此，我们有(n)个叶节点，以及(n-1)个内部节点。

总节点数= n + (n-1) = 2n-1。现在，我们知道它是一棵满二叉树，因此高度为: ceil(Log2(n)) +1

节点总数= 2^0 + 2^1 + 2^2 + … + 2^ceil(Log2(n)) // 这是等比数列，其中2^i表示第i层的节点数。

等比数列求和公式= 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的幂。也就是说，这个：

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

你可能会在这里看到与我的回答相同的内容。

- user3004790

---

难道不矛盾吗？首先提到节点总数为2 *（n-1）。接下来又说节点总数是2 * 2 ceil(Log2(n)) -1（我理解了其背后的解释）。但是，当n不是2的幂时，我们是否通过考虑2 * 2 ceil(Log2(n)) -1来分配额外的内存。假设线段树对于所有n都需要2 * n-1数组大小，因为2 * n-1是完全二叉树的总节点数，这也是线段树所需的。是这样吗？如果不是，那么分配2 * 2 ceil(Log2(n)) -1的目的是什么。 - dauntless

在最后一行，我认为你打错了。应该是“所以我们基本上需要比n大的最小2的幂（而不是n）”。 - shshnk

Answer 2

奇怪的是，当我查看问题时，我正在阅读和问题相同的来源。 我会尽力回答。

让我们从树的表示中（仅针对上下文）开始谈起：

1. 几乎是“最坏情况”。这个树不是完全平衡的，遍历起来并不容易。为什么？因为不同的输入可能会生成不同的树，因此遍历所需的时间无法预测。

2. 我们的“最佳情况”。 这个树是完全平衡或完整的，将花费可预测的时间进行遍历。此外，这棵树也更好地被“hack”。

现在让我们回到我们的问题。[参考第一张图片] 我们知道对于每一个n-input 数组（绿色数字），将有n-1个内部节点（蓝色数字）。因此，必须分配最多2n-1个节点空间。

但是这里的代码却相反。为什么？如何实现？

你预期的是：你期望为2n-1个节点分配的内存足够。换句话说，应该执行以下操作：

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

假设代码的其余部分正常工作，这并不是一个很好的想法。这是因为它创建了我们的不平衡树，就像我们第一种情况一样。这样的树不容易遍历，也不容易应用于解决问题。

实际发生的情况：我们使用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];

我们分配足够的空间来生成一个平衡完全树。这样的树易于遍历（使用一些特殊修改）并可直接应用于问题。

我们如何为case 2分配足够的内存？以下是方法：

• 我们知道我们的平衡线段树中至少有三个组成部分：

  1. 来自输入数组的n个数字。
  2. 必须的n-1个内部节点。
  3. 我们需要为padding分配的额外空间。

• 我们还知道具有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 的整数。

1. 是完全且可重复地被2整除，以获得一个完全平衡的二叉树。

- Quirk

---

请查看https://leetcode.com/problems/range-sum-query-mutable/solution/#nodebb-comments，并搜索“1.构建线段树。” 它不使用填充。它只使用2 * n数组来表示二叉树。（它以某种方式总是将其转换为完整树）它似乎是正确的。但没有任何解释。 - Weishi Z

@WeishiZeng 这样的树具有非常不直观的特性。输入数组元素应该成为叶子节点，每个节点的父节点应该是它的两个子节点值的和。但是，如果n不是2的幂（比如n = 5），这两个条件都不一定成立。 - mic

@mic 如果n = 5，输入数组元素仍然是叶子节点，但其中一些不在底层。具体来说，arr[0:2]在倒数第二层，而arr[3:4]在底层。隐式树将是[15 10 5 9 1 2 3 4 5]。这并不重要，因为我们仍然有tree[i] = tree[2i] + tree[2i+1]（基于1）。 - Zhiyong

Answer 3

假设输入数组大小为n。
所有输入数组元素都将成为线段树中的叶节点，因此叶节点数量=n。
由于线段树是一棵完全二叉树，所以线段树的高度h = ⌈Log₂n⌉ + 1。
高度为'h'的二叉树中最大节点数为2^h-1

因此，线段树中节点的数量为2^{⌈Log₂n⌉+1}-1
等于2*2^{⌈Log₂n⌉}-1。

- vijay yadav

---

段树不是一个完全二叉树，而是一个满二叉树，也就是说并不是所有层级都完全填满。 - undefined

Answer 4

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

线段树是一棵满二叉树。但我们要将其表示为一个数组。请注意，用数组表示高度为 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.

因此，线段树数组的大小 = [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。

- Vishnu Vivek

Answer 5

线段树将是一棵完全二叉树，其中所有叶子节点将表示您输入数组中的元素。如此处所述here。

完全二叉树中的节点数n至少为n = 2h+1 ，最多为n = 2^{h+1} - 1，其中 h 是树的高度。 h=log_2n。注意-log_2n表示以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

- Suyash Soni

Answer 6

这里有一些链接.. 从长度为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

- Rithik Singh

Answer 7

• n 是叶子节点的数量
• h 是树的高度

首先，线段树不是随机形成的二叉树。每个内部节点都有两个孩子。

如果一个线段树的高度为h，那么具有相同根但高度为h-1的树是一个完美二叉树，总共有2^(h-1)个节点。

来自visalgo

线段树是一种特殊的数据结构，类似于堆但不是一个完全二叉树（complete binary tree）。如下图所示，最后一层的叶子节点并不是从最左边开始填充。

我们已经知道线段树是一棵满二叉树，总节点数为n + (n - 1) = 2n - 1 = 2^(h-1) + k，其中k > 1表示深度为h的叶子节点数。很容易观察到k必须是偶数。

现在，我们可以推导出线段树的高度为h = log(2n - k) = 1 + floor(log(n - 1))

因此，总节点数为2^(h+1) - 1 = 2^(2+floor(log(n - 1)) - 1 = O(4n)

当线段树是一棵完美的二叉树时，就会达到这个数字。

- Izana