HELP needed with SIGSEGV using dynamic Segment TREE

december
fault
long_challenge
runtime-error
segmentation
trie

#1

I tried the problem www.codechef.com/problems/CBFEAST/ and could only come up with algorithms for 1st and 2nd subtask. For subtask 2 I planned to use segment trees, so I wrote a segment tree code for my own use.
The BUILD function gives a SIGSEGV error. I have tried the same TREE on leetcode and SPOJ and did not receive any segmentation fault.
For sub2 I build a segment tree representing 10^7 buckets and each bucket represents 100 colors for a total of 10^9 colors.
Please help me with this, to make it easy to help me I have figured out the following things :

  1. Even if I use a small n = 100 instead of 10^7, I receive SIGSEGV.
  2. Build function definitely leads to SIGSEGV, as I tried the code with only build and no other code.
  3. However when I used n = 64,I Did not receive SIGSEGV.

https://www.codechef.com/viewsolution/22008614
thankyou.


#2

Are you out-of-bounds on the array ar?
ar is an array length 10000000, and then I think you access it up to index 16777216?

One way to catch this sort of thing is to use vector ar(10000000) in place of ar[10000000].
Instead of accessing ar[x], you would use ar.at(x).
Any attempt to access outside the bounds of the array will crash with helpful message.


#3

Thanks for the reply and I’ll try using vector and report back, however I don’t feel this is the problem.
For leaf nodes I have assigned a 0 if node number greater than n.
Also I have tried the code without even using the array, had the code which used array commented out and only built the tree still got Same error.Thanks for the help will still try vector.


#4

Yes, you assign 0 if node greater than n.
But you have set n to be larger than the size of the ar array.

   n=16777216;
   SegmentTree<ll> sg(ar,n);

#5

https://www.codechef.com/viewsolution/22008321 check this please even n = 1000 gives SIGSEGV with build function.


#6

Thankyou, was able to fix my problem using vector.at() turns out problem was not with the tree but with my understanding of the question.