Segment tree [lazy propagation]

int n;
vector<ll> st, lazy;

void build(vector<ll>& T)
{
    for (n = 1; n < T.size(); n *= 2);
    st.resize(n * 2, 0), lazy.resize(n * 2, 0);

    for (int i = n; i < 2 * n; i++) st[i] = T[i - n];
    for (int i = n - 1; i > 0; i--) st[i] = f(st[l(i)], st[r(i)]);
}

inline void propagate(int v, int len)
{
    if (lazy[v] > 0)
    {
        st[v] += lazy[v] * len;
        if (len > 1) lazy[l(v)] += lazy[v], lazy[r(v)] += lazy[v];
        lazy[v] = 0;
    }
}

void update(int l, int r, int val, int v, int lhs, int rhs)
{
    if (lhs >= l && rhs <= r)
    {
        lazy[v] += val;
        propagate(v, rhs - lhs + 1);
    }
    else
    {
        propagate(v, rhs - lhs + 1);
        int m = lhs + (rhs - lhs) / 2;
        if (m >= l)     update(l, r, val, l(v), lhs, m);
        if (m + 1 <= r) update(l, r, val, r(v), m + 1, rhs);
        st[v] = f(st[l(v)], st[r(v)]);
    }
}
inline void update(int l, int r, int val)
{
    update(l, r, val, 1, 0, n - 1);
}

ll query(int l, int r, int v, int lhs, int rhs)
{
    propagate(v, rhs - lhs + 1);
    if (lhs >= l && rhs <= r)
        return st[v];
    int m = lhs + (rhs - lhs) / 2;
    return f((m < l ? def : query(l, r, l(v), lhs, m)),
        (m + 1 > r ? def : query(l, r, r(v), m + 1, rhs)));
}
inline ll query(int l, int r)
{
    return query(l, r, 1, 0, n - 1);
}