Ошибка Seg из-за malloc в конце программы C++

Question

Программа использует деревья сегментов, чтобы найти сумму заданного диапазона запроса. Это дает правильные ответы на введенные данные. Однако в конце программы после выполнения всех строк из главной функции отображается ошибка сегментации. Ссылка на изображение экрана вывода.

Сообщение об ошибке при выполнении прогона в GDB:

Программа получила сигнал SIGSEGV, Ошибка сегментации. 0x00007ffff71f0532 в __GI___libc_free (mem=0x617c60) в malloc.c:2967 2967 malloc.c: такого файла или каталога нет.

При обратном отслеживании с помощью GDB проблема, кажется, возникает в строке в начале основной функции, объявляющей векторные числа. Но я не вижу, что не так с моим кодом. Код, включающий деревья сегментов, кажется хорошим. Я тоже пытался использовать Valgrind, но ничего не понял.

Код (в C++):

#include <bits/stdc++.h>
using namespace std;

class NumArray
{
    public:
    int* st;
    vector<int> nums;
    NumArray(vector<int> num)
    {
        st = new int[num.size()];
        if(num.size() != 0)
        {
            st = constructST(num);
        }
        nums = num;
    }

    int* constructST(vector<int> nums)
    {
        int height = ceil(log(nums.size())/log(2));
        int stSize = 2*(int)pow(2,height)-1;
        constructSTUtil(nums,0,nums.size()-1,st,0);
        return st;
    }

    int constructSTUtil(vector<int> nums,int ss, int se, int* st,int si)
    {
        if(ss == se)
        {
            st[si] = nums[ss];
            return st[si];
        }
        int mid = ss + (se-ss)/2;
        st[si] = constructSTUtil(nums,ss,mid,st,2*si+1) + constructSTUtil(nums,mid+1,se,st,2*si+2);
        return st[si];
    }

    void update(int i, int val)
    {
        int diff = val - nums[i];
        nums[i] = val;
        int n = nums.size();
        updateUtil(st,0,n-1,i,diff,0);
    }

    void updateUtil(int* st,int ss,int se,int i,int diff,int si)
    {
        if(i < ss || i > se)
        {
            return;
        }
        st[si] = st[si] + diff;
        if(se != ss)
        {
            int mid = ss + (se-ss)/2;
            updateUtil(st,ss,mid,i,diff,2*si+1);
            updateUtil(st,mid+1,se,i,diff,2*si+2);
        }
    }

    int sumRange(int i, int j)
    {
        int n = nums.size();
        if(i < 0 || i > j || j > n)
        {
            cout << "Invalid input";
            return -32768;
        }
        return sumRangeUtil(st,0,n-1,i,j,0);
    }

    int sumRangeUtil(int* st,int ss, int se, int qs, int qe, int si)
    {
        if(qs <= ss && qe >= se)
        {
            return st[si];
        }
        if(qs > se || qe < ss)
        {
            return 0;
        }
        int mid = ss + (se-ss)/2;
        return sumRangeUtil(st,ss,mid,qs,qe,2*si+1) + sumRangeUtil(st,mid+1,se,qs,qe,2*si+2);
    }
};

int main()
{
    vector<int> nums;
    nums.push_back(0);
    nums.push_back(9);
    nums.push_back(5);
    nums.push_back(7);
    nums.push_back(3);
    NumArray obj(nums);
    cout << obj.sumRange(4,4) << "\n";
    cout << obj.sumRange(2,4) << "\n";
    cout << obj.sumRange(3,3) << "\n";
    obj.update(4,5);
    obj.update(1,7);
    obj.update(0,8);
    cout << obj.sumRange(1,2) << "\n";
    obj.update(1,9);
    cout << obj.sumRange(4,4) << "\n";
    cout << obj.sumRange(3,4) << "\n";
    return 0;
}

Answer 1

Посмотрите на эту функцию

int constructSTUtil(vector<int> nums,int ss, int se, int* st,int si)
{
    if(ss == se)
    {
        st[si] = nums[ss];
        return st[si];
    }
    int mid = ss + (se-ss)/2;
    st[si] = constructSTUtil(nums,ss,mid,st,2*si+1) + constructSTUtil(nums,mid+1,se,st,2*si+2);
    return st[si];
}

это называет это сам рекурсивно.

Теперь добавьте это coutв начале функции, например:

int constructSTUtil(vector<int> nums,int ss, int se, int* st,int si)
{
    cout << "ss = " << ss << " se = " << se << " si = " << si << endl;

когда nums есть 5 элементов, это даст вам:

ss = 0 se = 4 si = 0
ss = 0 se = 2 si = 1
ss = 0 se = 1 si = 3
ss = 0 se = 0 si = 7
              ^^^^^^
              ups... out of range for `st`

Итак, когда вы делаете:

st[si] = nums[ss];

Вы пишете вне границ. Другими словами, что-то не так с вашим алгоритмом.

КСТАТИ:

int stSize = 2*(int)pow(2,height)-1;
     ^^^^^
     Never used in the code

Также кажется довольно запутанным, что у вас есть член st а также аргумент функции st, И это также сбивает с толку, что вы назначаете st используя возвращаемое значение из constructsST (который st).