段樹2 * 2 ^（ceil（log（n））） - 1的數組的內存如何？

Question

鏈接：http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/。這是引用的文字：

我們以segment arr [0。 。 。 N-1]。每次我們將當前的段分成兩半（如果它還沒有成爲長度爲1的段），然後在兩半上調用相同的過程，並且對於每個這樣的段，我們將和存儲在相應的節點中。除最後一層以外，構建的分段樹的所有級別都將完全填充。此外，樹會成爲一個完整的二叉樹，因爲我們總是在每個級別分割兩部分。由於構造的樹總是具有n個葉子的完整二​​叉樹，因此將有n-1個內部節點。因此節點的總數將是2n - 1.段樹的高度將爲ceil [log（n）]。由於樹是使用陣列和父母和孩子之間的索引表示關係必須保持，分配用於線段樹內存容量將2 * 2 ^（小區（的log（n））） - 1。

如何是分配的內存（上面段的最後一行）那麼多？如果父代碼和子代碼是正確的，它們在代碼中如何存儲？請在此背後推理。如果這是錯誤的，那麼什麼是正確的價值？

Answer 1

這裏發生的事情是，如果你有一個n個元素的數組，那麼分段樹將爲這n個條目中的每一個都有一個葉節點。因此，我們有（n）個葉節點，還有（n-1）個內部節點。

節點= N +（N-1）= 2N-1的總數現在，我們知道它的滿二叉樹，因此高度：小區（LOG 2（N））+1

總沒有。節點= 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數組中的每個內部和葉節點都需要空間），因此它是大小數組。

= 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項！

而且，更好的解釋是：如果數組大小Ñ是2的冪，那麼我們有恰好n-1個內部節點，總結於2n-1個總節點。但並不總是，我們有n作爲2的冪，所以我們基本上需要最小的功率n這是大於n。這意味着此，

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

您可能會看到我相同的答案here

Answer 2

奇怪的是，我是從相同的源問題讀取時我來到這。我會盡力回答我最好的。

讓我們在樹表示基本的差異開始（在方面只）：

1. 的幾乎是「最壞情況」。這一個是不完全平衡並沒有真正有趣的遍歷。爲什麼？因爲在不同的投入下，可能會生成不同的樹，因此花費的時間不是很可預測的。

2. 我們的「最佳案例」場景。這一個是完全平衡或完成，並將需要一個可預測的時間來遍歷，總是。而且，這棵樹也更好「被黑」。

現在讓我們回到我們的問題。 [參考第一圖像]我們知道，對每n輸入陣列（數字在綠色），會有n-1個內部節點（數字在藍色）。所以最多需要分配2n-1節點空間。

但代碼here做了相反的事情。爲什麼和如何？

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分配足夠的內存？具體方法如下：

• 我們知道，在我們的平衡段樹至少有三個組成部分：

  1. ñ從我們的輸入數組數。
  2. n-1強制要求的內部節點。
  3. 我們需要爲我們的填充分配額外的空間。

• 我們也知道，與ķ葉平衡樹將有：

• 結合使用這兩種我們得到了想要的結果：

  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. 完全重複被2整除，得到完全平衡的2-ary（二進制）樹。

Answer 3

設輸入數組的大小爲n。
所有輸入數組元素將在線段樹的葉節點，因此數葉節點= N
由於線段樹是線段樹h的complete tree所以海特=⌈登錄Ñ⌉+ 1
中的高度 'H' 的二進制樹的節點的最大數目是2 ^ħ -1

因此，在一個段樹中的節點的總數= ^{2登錄⌈Ñ⌉+ 1} -1
等於2 * 2 ^{⌈登錄Ñ⌉} -1

Answer 4

線段樹將是一個全二叉樹，其中所有葉子會表示輸入數組中的元素。並作爲提here

節點的在一個完整的二叉樹Ñ數，是在 至少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