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)
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
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…
The correct formula would be
int nextPowOf2 = (int)round(pow(2, ceil(log2(arraySize))));
int treeSize = 2 * nextPowOf2 - 1;For anyone who stumbles upon this question later, I found this answer a little bit more helpful.
Important to note, \text{log}_2(N)=\text{log}_e(N)/\text{log}_e(2) so (\text{ceil})((\text{log}_e(N) / \text{log}_e(2)) + 1) = (\text{ceil})(\text{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.