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

Question

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

We start with the segment arr [0., n-1]. and each 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 save the amount in the corresponding node. All levels of the constructed segment tree will be completely filled, with the exception of the last level. In addition, the tree will be a complete binary tree, because we always divide the segments into two halves at each level. Since the constructed tree is always a complete binary tree with n leaves, there will be n-1 internal nodes. Thus, 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 an array, and the relationship between the parent and child indexes must be maintained, the size of the memory allocated for the segment tree will be 2 * 2 ^ (ceil (log (n))) - 1.

How is memory allocated (last line above)? How are parent and child indices stored in code if they are correct? Please explain this. If this is a lie, then what is the correct value?

Answer 1

What happens here if you have an array of n elements, then the segment tree will have a node leaf for each of these n records. Thus, we have (n) leaf nodes, as well as (n-1) inner nodes.

The total number of nodes = n + (n-1) = 2n-1 Now we know its complete binary tree and, therefore, the height: ceil (Log2 (n)) +1

Total No. 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.

The summation formula GP = a * (r ^ size - 1) / (r-1) where a = 2 ^ 0

Total No. 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 that are this number in number), so this is an array size.

= O (4 * n) approximately ...

You may also think so, this is a tree of segments:

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

If you are a segment tree above, then the array of segments array will be: 10,3,7,1,2,3,4, that is, the 0th element will store the sum of the 1st and 2nd records, the 1st record will be store the amount of 3, 4 and 2 will store the amount of the 5th and 6th records!

In addition, the best explanation: if the size of the array n is 2, then we have exactly n-1 internal nodes, adding up to 2n-1 . But we do not always have n as power 2, so we need the smallest degree n , which is greater than n . It means that

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

You can see my answer here.

Answer 2

Oddly enough, I read from the same source as the question, when did I understand this. I will try to answer all my questions.

Let's start with the main difference in tree views ( context only):

• Almost the worst case scenario. This one is not completely balanced , and not very fun to move around. What for? Because with different inputs different trees can be generated, and, therefore, the time spent on the traverse is not very predictable.

• Our scenario is "The best case." This one is fully balanced or complete , and a predictable amount of time will always pass. Moreover, this tree is also better “hacked”.

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

But the code here does the opposite. Why and how?

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

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

  Assuming the rest of the code works well, this is not a good idea. This is because it creates our unbalanced tree, as in our first case. Such a tree is not easy to navigate and easy to apply to problem solving.

• What really happens: We add / add extra memory with null or 0 values. We doing 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 create a balanced full tree. Such a tree can be easily moved (using some special modifications) and can be applied directly to problems.

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

• We know that in our balanced tree segment there are at least three components:

  • n from our input array.
  • n-1 , which are required.
  • Additional space that we need to allocate for our additions .

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

• Combining the two, we get the desired result:

   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 a level x above ensures that we get the closest integer number of ceilings, which:

• Greater than or equal to n (The number of elements in our input array).
• It is completely and repeatedly divided by 2 to get a fully balanced 2-ary (binary) tree.

Answer 3

Let the size of the input array be n.
All elements of the input array will be leaf nodes in the segment tree, so the number of leaf nodes = n
Since the segment tree is a complete tree , therefore, the height of the segment tree is h = ⌈ Log ₂ n ⌉ + 1
The maximum number of nodes in a binary tree with height "h" is 2 ^h -1

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

Answer 4

The segment tree will be a complete binary tree, where all leaves will indicate an element in your input array. And as mentioned here

The number of nodes n in the complete binary tree is in the least n = 2h + 1 and no more than 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 to determine the maximum number of nodes in a 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 

Answer 5

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

iterative implementation for constructing a tree of segments less than 4 * n in size from the array n (any number) https://codeforces.com/blog/entry/18051