Size of Segment Tree

maths
segment-tree
size

#1

About the space needed for segment tree, i came across the following equation

N = (ceil)((log(N) / log(2)) + 1)
size = 1 << N

interesting part is , the formula used natural logarithms, i.e, base ‘e’. I also read that upper limit of space required for segment tree is (4 * size of array)

  1. How to justify/derive this formula
  2. How this formula maximum value is 4 ?

#2

Let’s take the example of having the length of the array that you’re creating the segment tree as a power of 2 .

length of array, len = 2^x

Now in this case the number of nodes in its segment tree is 1 + 2 + 4 ... 2^x = 2^{x+1} -1

Therefore number of nodes in segment tree = 2*number\ of\ leaf\ nodes (Excluded the minus one since it’s just a constant)

Now let’s take the case when len is not a power of 2
In this case the segment number of leaf nodes = 2^{log(len)+1}

Therefore total number of nodes in the segment tree = 2*number\ of\ leaf\ nodes = 2 * 2^{log(len)+1} = 2^{log(len)+2} = 4 * len


#3

The base e is added by us for convenience. We know that ln(a)/ln(b) is log(a) with base (b)…Thus, we can easily remove the base e and work with base 2 if we want to…


#4

The correct formula would be

int nextPowOf2 = (int)round(pow(2, ceil(log2(arraySize))));

int treeSize = 2 * nextPowOf2 - 1;

#5

For anyone who stumbles upon this question later, I found this answer a little bit more helpful.

StackOverFlow


#6

The same question was asked in the interview of topbestof.


#7

Important to note, ext{log}_2(N)= ext{log}_e(N)/ ext{log}_e(2) so ( ext{ceil})(( ext{log}_e(N) / ext{log}_e(2)) + 1) = ( ext{ceil})( ext{log}_2(N)+1). So what you have there has nothing to do with the natural logarithm, it is just written in a strange way.