# Implement a segment tree (segtree) - errore update sum

**URL:** <https://forum.olinfo.it/t/implement-a-segment-tree-segtree-errore-update-sum/9012>\
**Category:** Aiuto\
**Created:** [12 Settembre 2024, 4:51pm UTC](https://forum.olinfo.it/t/implement-a-segment-tree-segtree-errore-update-sum/9012 "2024-09-12T16:51:49Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![marcome](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/b782af/32.png) [@marcome](https://forum.olinfo.it/u/marcome)\
**Post date:** [12 Settembre 2024, 4:51pm UTC](https://forum.olinfo.it/t/implement-a-segment-tree-segtree-errore-update-sum/9012/1 "2024-09-12T16:51:49Z")

</div>

Buonasera stavo provando a risolvere il problema [segtree](https://training.olinfo.it/#/task/segtree/statement) 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ì:

```auto
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:

```auto
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.

```auto
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";
    }
};

```

---

<div class="post-metadata">

**Author:** ![Mazza7](https://forum.olinfo.it/user_avatar/forum.olinfo.it/mazza7/32/2689_2.png) [@Mazza7](https://forum.olinfo.it/u/Mazza7)\
**Post date:** [13 Settembre 2024, 1:27pm UTC](https://forum.olinfo.it/t/implement-a-segment-tree-segtree-errore-update-sum/9012/2 "2024-09-13T13:27:39Z")

</div>

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

> [@marcome](#):
>
> ```c++
> N = a.size();
> tree.resize(2*N);
> 
> ```