GSS1 SPOJ - Runtime Error SIGSEGV

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\t";
    cin >> n ;

    //Input
    for(i = 1 ;i<=n;i++){
        cin >> arr[i];
    }
    //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 ;
}

The size of tree declared is wrong.

The size should be 2*2^(ceil(log2(n)) ~ 131100.

But one can safely always declare size of segment tree as 4*MAX

Also please prefer to paste the code on some other site such as pastebin, ideone and then share it’s link.

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

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

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.

See you have to mind some points while implementing a Binary Tree

  1. The height of tree of n nodes is log2 (n)
  2. The number of nodes of h height binary tree is pow (2, h + 1) - 1

So you should declare the tree array inside main() dynamically using pointer, as it is stored in the heap memory which has more size than the stack segment.

long long int *tree;
tree = new long long int [ (int) ( pow (2, h + 1) ) ];

Do this this should surely solve your problem.

Remember:

Static array declaration occurs inside the stack segment, dynamic array declaration occurs in the heap memory.

Do ask me for doubts.

Happy Coding! :slight_smile:

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

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

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.

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

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

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

The logic you have applied is wrong, try to understand the question, your code doesn’t output what is required.

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