メイン出口の後のセグメンテーションフォルト

Question

私はgdbで次のコードを実行しようとしましたが、gdbではセグメンテーションフォルトは表示されませんがgdbはありませんスタンドアロンモードで次のコードを実行すると、このコードは、セグメントツリーを使用して実装された範囲合計クエリに関連しています。

#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

segmentTree::constructUtilをv.size() == 3とします。その後、constructUtilへの最初の呼び出しにはstart == 0とend == 2があります。

したがって、mid = 1が得られます。

2番目の再帰呼び出しでは、start = 1,end = 2およびi = 2を渡します。 start != endであるため、elseが実行されます。

しかし、elseブロックa[(2*i)+2]にアクセスしています（ところで、そこには括弧が必要ありません）。このインデックスは6になります。

しかし、aのサイズを見ると、2*n-1となります。 2*3-1 = 5だから、6は明らかに範囲外です。

コードの意図はわかりませんが、未定義の動作があります。あなたはvalgrindのような何かを使って簡単にキャッチすることができます。a[...]をa.at(...)に置き換えることで、デバッグのためにgdbでコードを実行し、実際にすべての変数に従います（プログラムが未定義になる必要はありません問題を引き起こす可能性のあるあらゆる場所で可変内容のデバッグstd::coutステートメントを入力することによって、