×

No. of nodes in a segment tree.

 0 No. of nodes in a recursive segment tree of an array of size $n$ is $2n-1$. But still choosing $2n- 1$ as the size of segment tree gives a segmentation fault, and I have seen it in many places that it's recommended to use size of segment tree as $4n$. But why? Can someone clarify on this? asked 22 Jun '18, 15:31 825●1●13 accept rate: 13%

 1 @pshishod2645 , you can have a look to this link for a formal proof https://stackoverflow.com/questions/28470692/how-is-the-memory-of-the-array-of-segment-tree-2-2-ceillogn-1 answered 22 Jun '18, 15:41 121●7 accept rate: 6% Thanks @aman_robotics (22 Jun '18, 15:51)
 0 @pshishod2645 , If you like to build memory efficient program then you can build segment tree in iterative format. Then it will never use more than 2N memory and if you also want to have lazy propagation then it will require a total of 2N + N = 3*N memory ( extra N for lazy array ). :) answered 22 Jun '18, 16:16 4★meet2mky 201●3 accept rate: 26% Iterative version of segment tree is clear to me, I was just having a doubt about it's recursive version. (22 Jun '18, 16:30)
 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:

×2,738
×1,768
×316

question asked: 22 Jun '18, 15:31

question was seen: 171 times

last updated: 22 Jun '18, 16:30