You are not logged in. Please login at www.codechef.com 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, 15:31

pshishod2645's gravatar image

4★pshishod2645
814112
accept rate: 13%


link

answered 22 Jun, 15:41

aman_robotics's gravatar image

6★aman_robotics
1236
accept rate: 6%

(22 Jun, 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 ). :)

link

answered 22 Jun, 16:16

meet2mky's gravatar image

4★meet2mky
2013
accept rate: 28%

Iterative version of segment tree is clear to me, I was just having a doubt about it's recursive version.

(22 Jun, 16:30) pshishod26454★
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:

×2,579
×1,664
×294

question asked: 22 Jun, 15:31

question was seen: 143 times

last updated: 22 Jun, 16:30