Segment tree: lazy propagation

#include <bits/stdc++.h>
#define mid (left+right)/2
#define lson 2*idx,left,mid
#define rson 2*idx+1,mid+1,right
using namespace std;

const int N=4e5+10;

long long st[N], lazy[N];
int t;

void init (int idx, int left, int right)
{
    st[idx]=lazy[idx]=0;
    if (left<right) init(lson), init(rson);
}

void propagate (int idx, int left, int right)
{
    if (lazy[idx]!=0)
    {
        st[idx]+=lazy[idx]*(right-left+1);
        if (left<right)
        {
            lazy[2*idx]+=lazy[idx];
            lazy[2*idx+1]+=lazy[idx];
        }
        lazy[idx]=0;
    }
}

void update (int idx, int left, int right, int l, int r, long long val)
{
    propagate(idx, left, right);
    if (left>right || left>r || right<l) return;

    if (l<=left && right<=r)
    {
        st[idx]+=val*(right-left+1);
        if (left<right)
        {
            lazy[2*idx]+=val;
            lazy[2*idx+1]+=val;
        }
        return;
    }
    update(lson, l, r, val);
    update(rson, l, r, val);
    st[idx]=st[2*idx]+st[2*idx+1];
}

long long query (int idx, int left, int right, int l, int r)
{
    propagate(idx, left, right);
    if (left>right || left>r || right<l) return 0;

    if (l<=left && right<=r) return st[idx];
    return (query(lson, l, r)+query(rson, l, r));
}

void solve ()
{
    int n, q, op, l, r;
    long long val;

    scanf ("%d%d", &n, &q);
    init(1, 1, n);

    while (q--)
    {
        scanf ("%d%d%d", &op, &l, &r);
        if (op==1) printf ("%lld\n", query(1, 1, n, l, r));
        else
        {
            scanf ("%lld", &val);
            update (1, 1, n, l, r, val);
        }
    }
}

int main()
{
    scanf ("%d", &t);
    while (t--) solve();

    return 0;
}