×

# Number of nodes in a segment tree.

 0 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) This question is marked "community wiki". asked 17 May, 10:27 4★dbot_5 1●1 accept rate: 0%

 2 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. answered 17 May, 10:56 60●3 accept rate: 25% 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★
 0 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 answered 13 Jun, 11:04 5★meet2mky 111●3 accept rate: 40% 14.4k●1●13●52
 0 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. answered 13 Jun, 10:39 3★ay2306 192●9 accept rate: 13%
 0 Nice Method!! answered 14 Jun, 10:30 1★khiljee 19●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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