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

×

Number of nodes in a segment tree.

In the following implementation of segment tree, in the case when number of elements in the array for the range query, say A, are n such that n is not a power of 2, then I'm unable to establish that we actually require
2 * (pow(2,ceil((log2(n)))) - 1 nodes of the segment tree. In which case does the node variable's value in the following implementation may go past the 2*n-2 ?

https://onlinegdb.com/S1LMjFqCz (solution)

https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/range-minimum-query/ (problem statement)

This question is marked "community wiki".

asked 17 May, 10:27

dbot_5's gravatar image

4★dbot_5
11
accept rate: 0%

edited 17 May, 10:41


Consider an array of size 10. I will use 1 based indexing as it is convenient with array implementation of ST and Heaps. Refer to the following image, notice that the array[5](0 based) is at tree[24] (1 based index) and not $18$. $2*N$ size is only valid if it was a perfect binary tree. Alternative is to use $4*N$ size st tree. Read more about it in emaxx ru or gkcs's channel on youtube.

image here

Image

link

answered 17 May, 10:56

kukreja_vlk's gravatar image

4★kukreja_vlk
603
accept rate: 25%

edited 13 Jun, 21:08

1

The easiest way to see this, IMHO, is that if n is power of 2 then all the leaf nodes will lie at the same level(level log2(n), considering root at level 0). But if n is not a power of 2, some leaf nodes will lie at the next level, this is due to asymmetry in sibling nodes, one will have greater nodes than other and some of them will only leaf out at the next level. The caveat is the array implementation, since some of the leaf nodes are at next level, you will have to allocate twice as much memory because the implementation demands so, even though some array elements won't be used.

(17 May, 14:35) sorb19974★
1

Thanks pal @kukreja_vlk. Yes, I missed the case when both the segment will have odd nnumber of nodes.

(17 May, 15:25) dbot_54★

Well, It's depend on how you implement segment tree. Let's say you implemented segment tree in recursive format then, Yes! it will require $O(4*N)$ space in worst case. But if you will implement segment tree in iterative format then it will never use more than $O(2*N)$ space in any case or $O(3*N)$ space if lazy propagation is their. In iterative implementation of segment tree you do not need to allocate space for input because we directly read input in leaf of segment tree as we know that leaf node always represent our input. If you would like how it's done you can go through the below code.. Happy coding!!

View Content
link

answered 13 Jun, 11:04

meet2mky's gravatar image

5★meet2mky
1113
accept rate: 40%

edited 13 Jun, 18:46

vijju123's gravatar image

5★vijju123 ♦
14.4k11352

I understand your pain, I still don't remember that formula, that's why I use this code to determine the length of segment tree to declare

int tmp = n;
int count = 0;
while(tmp){
    count+=tmp;
    tmp/=2;
}

This is simple O(log(n)) code. Node causing any problem to anyone. So why not.

link

answered 13 Jun, 10:39

ay2306's gravatar image

3★ay2306
1929
accept rate: 13%

Nice Method!!

link

answered 14 Jun, 10:30

khiljee's gravatar image

1★khiljee
192
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,637
×675

question asked: 17 May, 10:27

question was seen: 246 times

last updated: 14 Jun, 10:30