Segment tree- sigsegv error

general
,
1

Sigsegv error is coming after submitting the following code,What is wrong with my code?

 #include<iostream>
 using namespace std;
 #define inf 0x7fffffff
 int arr[50000];   //WHY WE DEFINE IT GLOBALLLY
 int segtree[50000];   //WHY WE DEFINE IT GLOBALLY
 void constructtree(int low,int high,int pos);
 int rangemaxquery(int qlow,int qhigh,int low,int high,int pos);

 int main()
 {
 int m,xi,yi,y;
 long long int n,i;
 cin>>n;
 for(i=0;i<n;i++)
  {
   cin>>arr[i];
  }
 cin>>m;
 constructtree(0,i,0);
 while(m--)
  {
  cin>>xi>>yi;
  y=rangemaxquery(xi,yi,0,i,0);
  cout<<y<<"\n";
  }
 return 0;
 }

  void constructtree(int low,int high,int pos)
  {
  if (low==high)
   {
   segtree[pos]=arr[low];
   return ;

   }
   int mid=(low+high)/2;

    constructtree(low,mid,2*pos+1);
    constructtree(mid+1,high,2*pos+2);
    segtree[pos]=max(segtree[2*pos+1],segtree[2*pos+2]);

    }

   int rangemaxquery(int qlow,int qhigh,int low,int high,int pos)
    {
     if(qlow<=low&&qhigh>=high)
      return segtree[pos];

     if(qlow>high||qhigh<low)
     return -inf;//don't know

    int mid=(low+high)/2;
    return       max(rangemaxquery(qlow,qhigh,low,mid,2*pos+1),rangemaxquery(qlow,qhigh,mid+1,high,2*pos+2));
    }
2

Try increasing the side of declared arrays to 50010 maybe.

3

I’m afraid you have misinterpreted the problem statement a little. We have to find out the max{a[i]+a[i+1]+a[i+2]+…a[j]} for (x ≤ i ≤ j ≤ y). Put simply, we have to find sum of contiguous subarray in range (x,y) which has the largest sum. On the other hand, your code seems to be returning only the maximum number in that range, not maximum contiguous sum. That is the reason for the WA.

4

You misunderstand the question it is asking maximum contigous sum and also your segtree size is 50000 which is same as the size of array but is should be 2n-1 where n is the size of array element so if input array element is 50000 then your code will give sigsegv error means you are trying to access invalid memory means declare segtree size 2n-1

generally it is advised to declare 4 times of segtree size as many times of size of array size

5

sigsegv error because the size of segment tree is too less than the required one i.e.
if input size is power of 2 e.g. 4 then size of segment tree is 4 * 2 - 1=7
if input size is not power of two then take the number which just greater than the number and is the power of two e.g. if n=5 then size of segment tree is 8 * 2 - 1= 15

Also in solution you have used zero based indexing but while calling the query function e.g
y=rangemaxquery(xi,yi,0,i,0); used but you have to decrease xi and yi by 1 in call function
y=rangemaxquery(xi-1,yi-1,0,i,0);

in code we define array and segment tree globally so no need to write it again and again while calling constructtree() and rangemaxaquery() hope u got my point

6

No doesn’t work

7

Your logic is wrong somewhere maybe . I increased the memory bounds of both arrays and now we have is WA.

8

I modified it ,it is giving correct answer on test case given but on spoj it is giving WA ,now,i also optimized it for fast input output