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


No. of nodes in a segment tree.

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

pshishod2645's gravatar image

accept rate: 13%


answered 22 Jun '18, 15:41

aman_robotics's gravatar image

accept rate: 6%

(22 Jun '18, 15:51) pshishod26454★

@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

meet2mky's gravatar image

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) pshishod26454★
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 22 Jun '18, 15:31

question was seen: 171 times

last updated: 22 Jun '18, 16:30