Segment Tree Size Complexity

Revision en1, by vibster, 2018-08-25 05:45:55

Hey!

I was solving a problem on RMQ with the help of segment tree, but was consistently getting a SIGSEV error on submission. This was solved(gotAC) by making the size allocated for the segment tree to 6*n instead of 4*n. The segment tree implementation was a recursive one. Why did it need 6*n elements allocated since 4*n should be able to handle the worst case size.

Implementation: https://pastebin.com/usxY7ZgA Problem: https://www.spoj.com/problems/AKVQLD03/

Tags segment tree size, #segment tree, size complexity

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English vibster 2018-08-25 05:45:55 500 Initial revision (published)