GSS1 SPOJ - Runtime Error SIGSEGV

gss1
spoj

#1

Can anyone please explain me the reason why I’m getting a segmentation fault with this program

Problem Link : http://www.spoj.com/problems/GSS1/

#include<iostream>
#include<algorithm>
#include<cstring> //For memset
#include<climits>

#define MAX 50002 
#define inf LONG_MAX
using namespace std ;

long long arr[MAX];
long long tree[2*MAX + 1];

//function definition
//void update(long long node, long long a, long long b, long long i, long long j , long long value);
long long query(long long node , long long a , long long b , long long i , long long j);

void build_tree(long long node, long long a, long long b);

//function to find the middle value
inline long long getMid (long long a , long long b){
    return (a+b)/2;
}

//Find the maximum of three numbers
inline long long max(long long a , long long b , long long c){
    if (a > b){
        if(a > c)
            return a ;
        else 
            return c ;
    }
    else{
        if(b > c)
            return b ;
        else 
            return c ;
    }
}

//Build segment tree
void build_tree(long long node , long long a , long long b){
    if (a > b){
        return ; // out of range
    }
    if(a == b){
        tree[node] = arr[a];
        return ;
    }
    long long mid = getMid(a , b);
    build_tree(node*2 , a , mid);
    build_tree(node*2+1 , mid+1 , b );
    tree[node] = (tree[node*2] + tree[node*2 + 1]);
}

long long queryUtil(long long node , long long i , long long j){
    if(i == j){ //Leaf node
        return tree[node];
    }
    else{ //Other nodes
        long long mid = getMid( i , j);
        long long result = max(queryUtil(node*2 , i , mid) , queryUtil(node*2 + 1 ,mid+1 ,j) , tree[node]);
    }
}

//Query tree
long long query(long long node , long long a , long long b , long long i , long long j ){
    if(a > b || a > j || b < i)
        return -inf; // Out of range

    if(a >= i && b <= j) // Current segment is totally within range [i, j]
        return queryUtil(node , i , j); 

    long long mid = getMid(a , b);
    long long q1 = query(node*2, a, mid, i, j); // Query left child
    long long q2 = query(1+node*2, mid + 1, b, i, j); // Query right child

    long long res = max(q1 , q2);// Return final result
    
    return res;
}

//Driver Program
int main()
{
    long long n ,i , l , r , m ; 
    //cout << "Enter the number of elements in the array	";
    cin >> n ;

    //Input
    for(i = 1 ;i<=n;i++){
        cin >> arr*;
    }
    //initializing the array
    memset(tree , 0, sizeof(tree));
    //Build Tree
    build_tree(1 , 1, n);
    cin >> m ;
    while(m--){
        cin >> l >> r ;
        cout << query(1 , 1 , n , l , r) << endl;
    }
return 0 ;
}

#5

I have not read your full code, as the question said SIGSEGV, i just checked the array sizes and indexing in main function.


#6

If you feel your doubt was answered as per the question, mark it as accepted


#7

Hey @error_503_404,thanks for your answer, sorry for the delayed response ; but after changing it to 4*MAX, I am still getting a the same error. It would be great if you can help me to find the error.


#8

Do not forget to ceil() the log2(n) as it will take the upper bound for the height, which is a safe side.


#9

@bradley Still getting the same error. Don’t you think I made some other mistake ??


#10

Yes, in the queryutil() function you are not returning the result in the else clause.
Add return result in the ens of the else block.


#11

Still the same verdict at https://ideone.com/MfYp0j … Sorry for bothering you too much, but this has also become a pain in my ass. Please help


#12

@bradley, Please help me out. You are my only ray of hope now


#13

first try to make the solution correct,
try this input

5
3 -10 100 -2 20
1
1 5

your output = 111
Expected output = 118


#14

Oh yes ! You are correct. I need to change my logic