Lazy Propagation.cpp

/*  Lazy with propagation
    Update : l r v
             (add v from arr[l] to arr[r])
    Query  : l r
             (total sum from arr[l] to arr[r])
    Sample Problem : LightOJ-1164 (Horrible Queries)
*/

#include <bits/stdc++.h>

using namespace std;

#define MAX 100005
#define ll long long
ll arr[MAX];

struct data {
    ll val, prop;
} tree[4*MAX];

void init(ll node, ll b, ll e)
{
    if(b == e){
        tree[node].val = arr[b];
        tree[node].prop = 0;
        return;
    }
    ll left = 2*node;
    ll right = 2*node + 1;
    ll mid = (b+e)/2;
    init(left, b, mid);
    init(right, mid+1, e);
    tree[node].val = tree[left].val + tree[right].val;
    tree[node].prop = 0;
}

void update(ll node, ll b, ll e, ll i, ll j, ll x)
{
    if(i > e || j < b) return;
    if(b >= i && e <= j){
        tree[node].val += (e-b+1) * x;
        tree[node].prop += x;
        return;
    }
    ll left = 2*node;
    ll right = 2*node+1;
    ll mid = (b+e)/2;
    update(left, b, mid, i, j, x);
    update(right, mid+1, e, i, j, x);
    tree[node].val += tree[left].val + tree[right].val + (e-b+1)*tree[node].prop;
}

ll query(ll node, ll b, ll e, ll i, ll j, ll carry)
{
    if(i > e || j < b) return 0;
    if(b >= i && e <= j){
        return tree[node].val+(e-b+1)*carry;
    }
    ll left = 2*node;
    ll right = 2*node+1;
    ll mid = (b+e)/2;
    ll p = query(left, b, mid, i, j, carry+tree[node].prop);
    ll q = query(right, mid+1, e, i, j, carry+tree[node].prop);
    return p+q;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    ll cases;
    scanf("%lld", &cases);
    ll caseno = 0;
    while(cases--){
        printf("Case %lld:\n", ++caseno);
        ll n, q;
        scanf("%lld %lld", &n, &q);
        for(ll i=0; i<MAX; i++) arr[i] = 0;
        //memset(arr, 0, sizeof arr);
        init(1, 1, n);
        for(int i=1; i<=q; i++){
            ll type;
            scanf("%lld", &type);
            if(type == 0){
                ll x, y, v;
                scanf("%lld %lld %lld", &x, &y, &v);
                x++;
                y++;
                update(1, 1, n, x, y, v);
            }
            else {
                ll u, v;
                scanf("%lld %lld", &u, &v);
                u++;
                v++;
                ll res = query(1, 1, n, u, v, 0);
                printf("%lld\n", res);
            }
        }
    }
}