Segmentation fault after main exit

Question

I Have tried executing the following code in gdb, but with gdb I don`t see any segmentation fault but without gdb If I run the following code in standalone mode segmentation fault occurs. The code is related to range sum query implemented using segment tree.

#include <iostream>
#include <vector>
using namespace std;

class segmentTree
{
    private:
        vector<int> a;
        void constructUtil(vector<int>& , int , int , int );
        int queryUtil(int , int , int , int , int );
        void updateUtil(int , int , int , int , int );
    public:
        segmentTree(vector<int> );
        int query(int , int );
        void update(int , int );
        ~segmentTree();
};

segmentTree::segmentTree(vector<int> v)
{
    int n = v.size();
    a.resize((2*n) - 1);
    constructUtil(v, 0 , n - 1, 0);
}

segmentTree::~segmentTree()
{
    a.clear();
}

void segmentTree::constructUtil(vector<int>& v, int start, int end, int i)
{
    if(start == end)
    {
        a[i] = v[start];
    }
    else
    {
        int mid = start + ((end - start) >> 1);
        constructUtil(v, start, mid, ((2*i) + 1));
        constructUtil(v, mid + 1, end, ((2*i) + 2));
        a[i] = a[(2*i) + 1] + a[(2*i) + 2];
    }
}

int segmentTree::queryUtil(int ss, int se, int rs, int re, int i)
{
    if(se < rs || re < ss)
    {
        return 0;
    }
    else if(rs <= ss && se <= re)
    {
        return  a[i];
    }
    else
    {
        int sm = ss + ((se - ss) >> 1);
        return queryUtil(ss, sm, rs, re, 2*i + 1) + queryUtil(sm + 1, se, rs, re, 2*i + 2);
    }
}

int segmentTree::query(int l, int r)
{
    int n = ((a.size() + 1) >> 1);
    if(l < 0 || r > n-1)
    {
        return 0;
    }
    return queryUtil(0, n-1, l , r, 0);
}

void segmentTree::updateUtil(int ss, int se, int i, int si, int x)
{
    if(ss > i || se < i)
    {
        return ;
    }
    else if(ss == se)
    {
        a[si] = x;
    }
    else
    {
        int sm = ss + ((se - ss) >> 1);
        updateUtil(ss, sm, i, (2*si) + 1, x);
        updateUtil(sm + 1, se, i, (2*si) + 2, x);
        a[si] = a[(2*si) + 1] + a[(2*si) + 2];
    }
}

void segmentTree::update(int i, int x)
{
    int n = ((a.size() + 1) >> 1);
    if(i < 0 || i > n-1)
    {
        return ;
    }
    else
    {
        updateUtil(0, n-1, i, 0, x);
    }
}

int main()
{
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    vector<int> v(arr, arr + n);

    segmentTree st(v);

    // Print sum of values in array from index 1 to 3
    cout << "Sum of values in given range = " << st.query(1, 3) << endl;

    // Update: set arr[1] = 10 and update corresponding 
    // segment tree nodes
    st.update(1, 10);

    // Find sum after the value is updated
    cout << "Updated sum of values in given range = " << st.query(1, 3) << endl;
    return 0;
}

Answer 1

Consider segmentTree::constructUtil with v.size() == 3. Then in the inital call to constructUtil you have start == 0 and end == 2.

Thus we get mid = 1.

In the second recursive call we are then passing start = 1, end = 2 and i = 2. start != end and so the else is executed.

However in the else block a[(2*i)+2] is accessed (by the way, no need for the parantheses there). This index will be 6.

But if you look at the size of a, it was given as 2*n-1. 2*3-1 = 5, so 6 is clearly out-of-bounds.

I don't know what your intentions with the code are, but that there is undefined behavior. You can easily catch it by either using something like valgrind, by replacing a[...] with a.at(...) for debug purposes, by stepping through the code with gdb and actually following all the variables (there does not need to be a segmentation fault for your program to have undefined behavior) or by entering debug std::cout statements with the variable content everywhere that could cause the issue.