You are not logged in. Please login at www.codechef.com to post your questions!

×

Size of Segment Tree

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 ?

asked 16 Sep '16, 14:42

ashwanigautam's gravatar image

3★ashwanigautam
187213
accept rate: 0%

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.

(04 Dec, 16:45) gorre_morre7★

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$

link

answered 16 Sep '16, 16:37

bhishma's gravatar image

4★bhishma
2977
accept rate: 11%

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

link

answered 05 Mar, 00:24

bluescorp's gravatar image

3★bluescorp
111
accept rate: 0%

edited 05 Mar, 00:25

The correct formula would be

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

int treeSize = 2 * nextPowOf2 - 1;
link

answered 05 Mar, 01:03

dollarakshay's gravatar image

4★dollarakshay
17617
accept rate: 4%

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

StackOverFlow

link

answered 02 Dec, 19:18

anachronewbie's gravatar image

3★anachronewbie
1
accept rate: 0%

The same question was asked in the interview of topbestof.

link

answered 05 Dec, 21:10

yash005's gravatar image

1★yash005
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,703
×1,163
×22

question asked: 16 Sep '16, 14:42

question was seen: 4,653 times

last updated: 05 Dec, 21:10