Segmentation fault in std::vector destructor

Question

I was trying to solve a problem on SPOJ (http://www.spoj.com/problems/GSS1) & ended up making the following code using Segment Tree. The code works pretty fine. But on some inputs , it gives a segmentation fault, peculiarly at the end of the program, when it tries to de-allocate memory of vector from the stack. I have spent quite a lot of time already, but am unable to find any mistake. Any help would be highly appreciated.

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

struct Node{
    int bend;
    int bsum;

    int ebeg;
    int esum;
    int maxSum;

    Node(): bend(0), bsum(0), ebeg(0), esum(0), maxSum(0){}
    Node(const Node& other): bend(other.bend), bsum(other.bsum), ebeg(other.ebeg), esum(other.esum), maxSum(other.maxSum){}
    ~Node(){}
};

class SegmentTree{
    int N;
    vector<Node> M;
    vector<int> A;

    public:

    SegmentTree(int N){
        this -> N = N;
        Node temp;
        M.resize((1 << ((int)log(N)+2))+1, temp);
    }

    SegmentTree(const SegmentTree& other): N(other.N), M(other.M), A(other.A) {}

    ~SegmentTree(){
        M.clear();
        A.clear();
    }


    void put(int a){
        A.push_back(a);
    }

    void initialize(int node, int b, int e)
    {
        if (b == e){
            M[node].bsum = M[node].esum = A[b];
            M[node].bend = M[node].ebeg = b;
            if (A[b] > 0) M[node].maxSum = A[b];
            else M[node].maxSum = 0;
        }

        else
        {
            //compute the values in the left and right subtrees
            int boundary = (b+e)/2;
            initialize(2 * node, b, boundary);
            initialize(2 * node + 1, boundary + 1, e);

            //maxSum
            M[node].maxSum = max( M[2*node].esum+M[2*node+1].bsum, max(M[2*node].maxSum, M[2*node+1].maxSum));

            //bsum
            M[node].bsum = M[2*node].bsum;
            if(M[2*node].bend == boundary && M[2*node+1].bsum >= 0) M[node].bsum += M[2*node+1].bsum, M[node].bend = M[2*node+1].bend;
            else M[node].bend = M[2*node].bend;

            //esum
            M[node].esum = M[2*node+1].esum;
            if(M[2*node+1].ebeg == boundary + 1 && M[2*node].esum >= 0) M[node].esum += M[2*node].esum, M[node].ebeg = M[2*node].ebeg;
            else M[node].ebeg = M[2*node+1].ebeg;
        }
    } 

    Node query(int node, int b, int e, int i, int j)
    {
        Node ret;
        ret.maxSum = -1;

        //if the current interval doesn't intersect
        //the query interval return -1
        if (i > e || j < b)
            return ret;

        //if the current interval is included in 
        //the query interval return M[node]
        if (b >= i && e <= j)
            return M[node];

        //use left and right part of the interval
        Node p1, p2;
        int boundary = (b+e)/2;
        p1 = query(2 * node, b, boundary, i, j);
        p2 = query(2 * node + 1, boundary + 1, e, i, j);
        if (p1.maxSum == -1)
            return p2;
        if (p2.maxSum == -1)
            return p1;

        //maxSum
        ret.maxSum = max(p1.esum + p2.bsum, max(p1.maxSum, p2.maxSum));
        //bsum
        ret.bsum = p1.bsum;
        if(p1.bend == boundary && p2.bsum >= 0) ret.bsum += p2.bsum, p1.bend = p2.bend;
        else ret.bend = p1.bend;
        //esum
        ret.esum = p2.esum;
        if(p2.ebeg == boundary + 1 && p1.esum >= 0) ret.esum += p1.esum, M[node].ebeg = p1.ebeg;
        else ret.ebeg = p2.ebeg;
        return ret;
    }
};

int main(){
    int N;
    cin >> N;
    SegmentTree tree(N);
    for (int i = 0; i < N; i++){
        int a;
        cin >> a;
        tree.put(a);
    }

    tree.initialize(1, 0, N-1);
    int M;
    cin >> M;
    while(M--){
        int x, y;
        cin >> x >> y;
        Node ans;
            ans = tree.query(1, 0, N-1, x-1, y-1);
        cout << ans.maxSum << endl;
    }
}

For example, on input:

9
-2 1 -3 4 -1 2 1 -5 4
1
1 9

the program gives segmentation fault at the end of the program. The backtrace is as follows:

(gdb) backtrace
#0  0x4e584494 in malloc_consolidate () from /lib/libc.so.6
#1  0x4e584f1d in _int_free () from /lib/libc.so.6
#2  0x4eb54500 in operator delete(void*) () from /lib/libstdc++.so.6
#3  0x0804a581 in __gnu_cxx::new_allocator<int>::deallocate (this=0xbfffee68, __p=0x804f1c0) at /usr/lib/gcc/i686-redhat-linux/4.7.2/../../../../inclu
de/c++/4.7.2/ext/new_allocator.h:100
#4  0x08049e21 in std::_Vector_base<int, std::allocator<int> >::_M_deallocate (this=0xbfffee68, __p=0x804f1c0, __n=16) at /usr/lib/gcc/i686-redhat-lin
ux/4.7.2/../../../../include/c++/4.7.2/bits/stl_vector.h:175
#5  0x080498ff in std::_Vector_base<int, std::allocator<int> >::~_Vector_base (this=0xbfffee68, __in_chrg=<optimized out>) at /usr/lib/gcc/i686-redhat
-linux/4.7.2/../../../../include/c++/4.7.2/bits/stl_vector.h:161
#6  0x08049628 in std::vector<int, std::allocator<int> >::~vector (this=0xbfffee68, __in_chrg=<optimized out>) at /usr/lib/gcc/i686-redhat-linux/4.7.2
/../../../../include/c++/4.7.2/bits/stl_vector.h:404
#7  0x08048dcb in SegmentTree::~SegmentTree (this=0xbfffee58, __in_chrg=<optimized out>) at test.cpp:35
#8  0x08048b7b in main () at test.cpp:134

As you can see, the error occurs on the call to ~SegmentTree(). The control doesn't even shift to M.clear() (which should ideally de-allocate memory) and results in segmentation fault. So, what is the reason for this segmentation fault?

Thanks for your help!

Answer 1

The most likely reason is that you've got a memory corruption somewhere in your program. If I had to guess, I'd say that you probably have an out-of-bounds write to M[].

Try running the program under valgrind.