vibster's blog

By vibster, history, 6 years ago, In English

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/

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

In your build function, even when you've assigned some value to leaf node, you're still taking the sum of 2*node and 2*node+1. That will overflow from regular 4*n, causing SIGSEV.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Damn, that was a trivial mistake. Thanks man!