Implement a segment tree (segtree) - errore update sum

Aiuto
1

Buonasera stavo provando a risolvere il problema segtree ed ho seguito la guida sul forum per implementare il segment tree, solo non capisco come mai non faccia bene gli update delle somme.

Ad esempio sul testcase della traccia inizializza il segment così:

0 -9 33 -42 2 11 -13 -29 17 -15 13 -2 -6 -15 -25 -4 0 0 0 0

E dopo il primo update:

0 6944657528489791512 6944657528489791554 -42 10 6944657528489791544 -13 -29 21 -11 -22 6944657528489791566 -6 -15 -25 -4 0 0 0 0

Sembra acceda ad un’area di memoria non inizializzata ma non vedo veramente dove.

struct superTree
{
    struct node {ll sum = 0, min = 1e18, lazy = 0;};

    int N;
    vector<node> tree;

    superTree() {}
    superTree(vector<ll> &a)
    {
        N = a.size();
        tree.resize(2*N);
        build(1, 0, N, a);
    }

    node build(int i, int l, int r, vector<ll> &a)
    {
        if (r - l == 1) return tree[i] = {a[l], a[l], 0};

        int m = (l + r) / 2;
        tree[i].sum = build(2*i, l, m, a).sum + build(2*i+1, m, r, a).sum;
        tree[i].min = min(build(2*i, l, m, a).min, build(2*i+1, m, r, a).min);

        return tree[i];
    }

    void propagate (int i, int l, int r)
    {
        if (tree[i].lazy == 0) return;

        tree[i].sum += tree[i].lazy * (r - l);
        tree[i].min += tree[i].lazy;

        if (r - l > 1)
        {
            tree[2*i].lazy += tree[i].lazy;
            tree[2*i+1].lazy += tree[i].lazy;
        }

        tree[i].lazy = 0;
    }

    void addRange (int i, int l, int r, int ql, int qr, ll x)
    {
        propagate(i, l, r);
        if (qr <= l || r <= ql) return;
        if (ql <= l && r <= qr)
        {
            tree[i].lazy += x;
            propagate(i, l, r);
            return;
        }

        int m = (l + r) / 2;
        addRange(2*i, l, m, ql, qr, x);
        addRange(2*i+1, m, r, ql, qr, x);

        tree[i].sum = tree[2*i].sum + tree[2*i+1].sum;
        tree[i].min = min(tree[2*i].min, tree[2*i+1].min);
    }

    void add (int l, int r, ll x) {addRange(1, 0, N, l, r, x);}

    void setRange (int i, int l, int r, int ql, int qr, ll x)
    {
        propagate(i, l, r);
        if (qr <= l || r <= ql) return;
        if (ql <= l && r <= qr)
        {
            tree[i].lazy = x;
            propagate(i, l, r);
            return;
        }

        int m = (l + r) / 2;
        setRange(2*i, l, m, ql, qr, x);
        setRange(2*i+1, m, r, ql, qr, x);

        tree[i].sum = tree[2*i].sum + tree[2*i+1].sum;
        tree[i].min = min(tree[2*i].min, tree[2*i+1].min);
    }

    void set (int l, int r, ll x) {setRange(1, 0, N, l, r, x);}

    ll sumQuery (int i, int l, int r, int ql, int qr)
    {
        propagate(i, l, r);
        if (qr <= l || r <= ql) return 0;
        if (ql <= l && r <= qr) return tree[i].sum;

        int m = (l + r) / 2;
        return sumQuery(2*i, l, m, ql, qr) + sumQuery(2*i+1, m, r, ql, qr);
    }

    ll sumQ (int l, int r) {
        // cout << endl;
        // for (int i = 0; i < 2*N; i++)
        //     cout << tree[i].sum << " ";
        // cout << "\n";
        return sumQuery(1, 0, N, l, r);}

    ll minQuery (int i, int l, int r, int ql, int qr)
    {
        propagate(i, l, r);
        if (qr <= l || r <= ql) return 1e18;
        if (ql <= l && r <= qr) return tree[i].min;

        int m = (l + r) / 2;
        return min(minQuery(2*i, l, m, ql, qr), minQuery(2*i+1, m, r, ql, qr));
    }

    ll minQ (int l, int r) {return minQuery(1, 0, N, l, r);}

    void print()
    {
        cout << endl;
        for (node n : tree)
            cout << n.sum << " ";

        cout << "\n";

        for (node n : tree)
            cout << n.min << " ";
        
        cout << "\n";
    }
};
2

Qui devi fare il resize a 4 * N per essere sicuro di non accedere ad indici fuori dai limiti