segment tree template

class node
{
public:
    int mx, l, r, sum;

    node operator+(node b)
    {
        return {
            max({r + b.l, mx, b.mx}), max({l, sum + b.l}), max({b.r, b.sum + r}), sum + b.sum};
    };
};
class SGT
{
public:
    vector<int> seg, lazy;

    SGT(int n)
    {
        seg.resize(4 * n + 1);
        lazy.resize(4 * n + 1);
    }
    void build(int ind, int low, int high, vector<int> &arr)
    {

        if (low == high)
        {
            seg[ind] = arr[low];
            return;
        }
        int mid = low + ((high - low) >> 1);

        build((2 * ind) + 1, low, mid, arr);
        build((2 * ind) + 2, mid + 1, high, arr);

        seg[ind] = (seg[(2 * ind) + 1] + seg[(2 * ind) + 2]);
    }
    void propogate(int ind, int low, int high, int val)
    {
        seg[ind] += val;
        if (low != high)
        {
            lazy[2 * ind + 1] += val;
            lazy[2 * ind + 2] += val;
        }
        lazy[ind] = 0;
    }
    int query(int ind, int low, int high, int l, int r)
    {
        propogate(ind, low, high, lazy[ind]);
        // no overlap
        if (l > high || r < low)
            return 0;

        // complete overlap
        if (low >= l && r >= high)
            return seg[ind];
        int mid = low + ((high - low) >> 1);
        int left = query(2 * ind + 1, low, mid, l, r);
        int right = query(2 * ind + 2, mid + 1, high, l, r);
        return (left + right);
    }

    void update(int ind, int low, int high, int i, int val, vector<int> &arr)
    {
        propogate(ind, low, high, lazy[ind]);
        if (low == high)
        {
            seg[ind] = val;
            lazy[ind] = val;
            propogate(ind, low, high, lazy[ind]);
            return;
        }
        int mid = low + ((high - low) >> 1);
        if (i <= mid)
            update(2 * ind + 1, low, mid, i, val, arr);
        else
            update(2 * ind + 2, mid + 1, high, i, val, arr);
        seg[ind] = (seg[2 * ind + 1] + seg[2 * ind + 2]);
    }
};