SegmentTree

struct node {
    ll val, lazy;
    node(ll _val = 0, ll _lazy = 0) :
     val(_val), lazy(_lazy) {}
};

struct SegmentTree {
    const node invalid = node(INF,0);

    int size;
    vector<int> l, r;
    vector<node> tree;

    node val(node t) {
        t.val += t.lazy;
        t.lazy = 0;
        return t;
    }

    void updLazy(node& t, ll v) {
        t.lazy += v;
    }

    node best(node x, node y) {
        return x.val < y.val ? x : y;
    }

    void modify(int i) {
        tree[i] = best(val(tree[i << 1]), val(tree[i << 1 | 1]));
    }

    void prob(int i) {
        updLazy(tree[i << 1], tree[i].lazy);
        updLazy(tree[i << 1 | 1], tree[i].lazy);
        tree[i].lazy = 0;
    }

    SegmentTree(int _size) :
     size(_size), l(4 * _size), r(4 * _size) , tree(4 * _size) {
            init(0, _size - 1);
         }

     void update(int s, int e, ll v, int i = 1) {
         if (s > r[i] || e < l[i])
            return;

        if (l[i] >= s && r[i] <= e) {
            updLazy(tree[i], v);
            return;
        }

        prob(i);

        update(s, e, v, i << 1);
        update(s, e, v, i << 1 | 1);

        modify(i);
     }

     node query(int s, int e, int i = 1) {
         if (s > r[i] || e < l[i])
            return invalid;

        if (l[i] >= s && r[i] <= e) {
            return val(tree[i]);
        }

        prob(i);

        node lhs = query(s, e, i << 1);
        node rhs = query(s, e, i << 1 | 1);

        modify(i);

        return best(lhs, rhs);
     }

    void init(int s, int e, int i = 1) {
        l[i] = s;
        r[i] = e;

        if (s == e)
            return;

        int m = s + ((e - s) >> 1);

        init(s, m, i << 1);
        init(m + 1, e, i << 1 | 1);
    }
};