How is the memory of the array of segment tree 2 * 2 ^(ceil(log(n))) - 1?

Question

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

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 .

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 the reasoning behind this. If this is false, then what is the correct value?

Bamford

Answer 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.

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

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.

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

Total no. of nodes = 1*(2^(ceil(Log2(n))+1) -1)/(2-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) approx..

You may also think of it this way, Let the below be the segment tree:

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

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 3rd and 4th and 2nd will store the sum of 5th and 6th entry!!

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 2 which is greater than n. That means this,

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

You may see my same answer here

Leanora

Isn't there a contradiction? As in first it has been mentioned that the total no. of nodes is 2*(n-1).Next it is said that the total no. of nodes is 2* 2 ceil(Log2(n)) -1(I understood the explanation behind that). But aren't we allocating extra memory by considering 2* 2 ceil(Log2(n)) -1 when n is not a power of 2. Is it right to assume that a segment tree requires 2* n-1 array size for all n since 2* n-1 is the total no. of nodes for a full binary tree and that is what is required in a segment tree. Is that right? If not what is the purpose behind allocating 2* 2 ceil(Log2(n)) -1. – Bamford

in the last line i think you have a typo. it should be "so we basically need the smallest power of 2 (not n) which is greater the n" – Rockie

The last line of code should be for(; s<2*n; s<<=1);, because we want a complete tree that can fit the 2*n total number of nodes. – Roadbed

Answer 2

Oddly enough, I was reading from the same source as the question when I came upon this. I'll try and answer my best.

Let's start with a basic difference in trees representations (in context only):

1. The almost "Worst Case" scenario. This one is not completely balanced and not really fun to traverse. Why? Because, with different inputs, different trees might be generated and hence time taken to traverse is not very predictable.

2. Our "Best Case" scenario. This one is totally balanced or complete and will take a predictable amount of time to traverse, always. Moreover, this tree is also better "hacked".

Now let's get back to our question. [Refer to the first image] We know that for every n-input array (The numbers in green), there will be n-1 internal nodes (The numbers in blue). So a maximum of 2n-1 node space must be allocated.

But the code here does something on the contrary. Why and how?

1. What you expect: You expect that the memory allocated for 2n-1 nodes should be sufficient. In other words, this should be done:

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

   Assuming the rest of the code works well, this is isn't a very good idea. That's because it creates our unbalanced tree, much like in our first case. Such a tree is not easy to traverse nor easy to apply to problem-solving.

2. What really happens: We add/pad extra memory with null or 0 values. We do this:

   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];
   

   That is we allocate enough space to generate a balanced complete tree. Such a tree is easy to traverse (using some special modifications) and can be applied to problems directly.

How did we allocate enough memory for case 2? Here's how:

• We know there are at least three components in our balanced Segment Tree:

  1. n numbers from our input array.
  2. n-1 internal nodes which are mandatorily required.
  3. The extra space we need to allocate for our padding.

• We also know that a balanced tree with k leaves will have:

• Combining the two we get the desired outcome:

  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];
  

Trivia! Raising 2 to the power of x above, ensures that we get the nearest ceiling integer which is:

1. Greater than or equal to n (Number of elements in our input array).
2. Is perfectly and repeatedly divisible by 2, to get a completely balanced 2-ary (binary) tree.

Anstice

check out leetcode.com/problems/range-sum-query-mutable/solution/… and search for 1. Build segment tree. it doesn't use padding. It only uses 2*n array to represent the binary tree. (it somehow always transformed it into a complete tree) And it seems correct. But it's not explained anywhere. – Squawk

@WeishiZeng Such a tree has very unintuitive properties. The input array elements are supposed to become leaves, and the parent of each node is supposed to be the sum of its two children's values. But neither of these is is necessarily the case if n is not a power of 2 (say, if n = 5). – Earing

@Earing If n = 5, the input array elements are still leaves, but some of them are not at the bottom layer. Specifically, arr[0:2] are on the last 2nd level, while arr[3:4] are on the bottom level. The implicit tree will be [15 10 5 9 1 2 3 4 5]. It doesn't matter because we still have tree[i] = tree[2i] + tree[2i+1] (1-based). – Latimore

Answer 3

Let the size of input array is n.
All the input array elements will be leaf nodes in segment tree so the number of leaf nodes = n
Since the Segment tree is a complete tree so the Hight of Segment Tree h = ⌈ Log₂n ⌉ + 1
Maximum number of nodes in a binary tree of height ‘h’ is 2^h-1

So Number of nodes in a segment tree = 2^{⌈ Log₂n ⌉ + 1} -1
Equals to 2*2^{⌈ Log₂n ⌉} -1

Smithson

isn't segment tree a full binary tree rather than a complete binary tree? i.e. not all levels are completely filled – Styliform

Answer 4

How to determine the required size of the Segment Tree Array?

Segment tree is a full binary tree. But we are representing it in an array. Remember, representing any Binary Tree of height h in an array representation, will require the space equivalent to a Perfect Binary Tree of height 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

The given array will represent the leaves of the segment tree. So, the size of the given array will be the no. of leaves.

In a segment tree, every pair of leaves will be joined by their parent in the previous level. And these parents will again be joined by their parents at the previous level. This goes on until the root.

Example:

* 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.

Talking generally,

* 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.

Thus, Size of the Segment Tree Array = [2*2 ^ (Ceil[ Log_2 (N) ] )] - 1

Size of the Segment Tree Array is simply 4N (approx.).

Example:

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.

Talking generally,

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.)

Thus, Size of the Segment Tree Array = 4N (approx.)

Scape

Answer 5

Segment tree will be a full-binary tree where all leaves will denote the element in your input array. And as mention 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

Here is the python code for finding out maximum number of nodes in segment tree -

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

Caballero

Answer 6

here are some links .. iterative implementation for building segment tree of size 2*n-1 from array of n(any number) length https://www.geeksforgeeks.org/segment-tree-efficient-implementation/ recursive implementation for building segment tree of size 2*n-1 from array of n(any number) length https://www.hackerearth.com/practice/notes/segment-tree-and-lazy-propagation/#c191521

iterative implementation for building segment tree of size less than 4*n from array of n(any number) https://codeforces.com/blog/entry/18051

Substratosphere

Answer 7

• n is the number of leaves
• h is the height

First thing, segment tree is not a random formed binary tree. each internal nodes have 2 children.

If the height of a segment tree is h, then the tree with the same root but with height h-1 is a perfect binary tree, with 2^(h-1) total nodes.

from visalgo

Segment tree is special, it's like heap but it's not a complete binary tree. See pic below, the last level leaves are not filled from the leftmost position.

We already know a segment tree is a full binary tree, total node is n + (n - 1) = 2n - 1 = 2^(h-1) + k, where k > 1 and represents number of leaves at depth h. And it's easy to observe that k must be an even number.

Now, we can derive the height is h = log(2n - k) = 1 + floor(log(n - 1))

then to total node is 2^(h+1) - 1 = 2^(2+floor(log(n - 1)) - 1 = O(4n)

This number is reached when the segment tree is a perfect binary tree.

Haemostat