LOJ 1164 seg

#include<bits/stdc++.h>
using namespace std;

typedef long long int      ll;

#define Max 2000009
#define MAX 2147483647
#define read()             freopen("input.txt", "r", stdin)
#define write()            freopen("output.txt", "w", stdout)

ll Tree[Max],lazy[Max];

void UpdateLazy(int node,int L,int R,int x,int y,ll val)
{
    int mid = (L+R)/2;
    int Left = 2*node;
    int Right = Left+1;
    if(lazy[node]){
        Tree[node]+=(R-L+1)*lazy[node];
        if(L!=R){
            lazy[Left]+=lazy[node];
            lazy[Right]+=lazy[node];
        }
        lazy[node]=0;
    }
    if(L>y || R<x) return;
    if(L>=x && R<=y){
        Tree[node]+=(R-L+1)*val;
        if(L!=R){
            lazy[Left]+=val;
            lazy[Right]+=val;
        }
        return;
    }
    UpdateLazy(Left,L,mid,x,y,val);
    UpdateLazy(Right,mid+1,R,x,y,val);
    Tree[node] = Tree[Left]+Tree[Right];
}

ll RangeSum(int node,int L,int R,int x,int y)
{
    int mid = (L+R)/2;
    int Left = 2*node;
    int Right = Left+1;
    if(lazy[node]){
        Tree[node]+=(R-L+1)*lazy[node];
        if(L!=R){
            lazy[Left]+=lazy[node];
            lazy[Right]+=lazy[node];
        }
        lazy[node]=0;
    }
    if(L>y || R<x) return 0;
    if(L>=x && R<=y){
        return Tree[node];
    }
    ll sum1 = RangeSum(Left,L,mid,x,y);
    ll sum2 = RangeSum(Right,mid+1,R,x,y);
    return sum1+sum2;
}


int main()
{
    //read();
    //write();
    int t;
    scanf("%d",&t);
    for(int j=1;j<=t;j++){
        int n,q,k,x,y;
        ll v;
        scanf("%d %d",&n,&q);
        memset(Tree,0,sizeof(Tree));
        memset(lazy,0,sizeof(lazy));
        printf("Case %d:\n",j);
        for(int i=0;i<q;i++){
            scanf("%d",&k);
            if(!k){
                scanf("%d %d %lld",&x,&y,&v);
                UpdateLazy(1,1,n,x+1,y+1,v);
            }
            else{
                scanf("%d %d",&x,&y);
                printf("%lld\n",RangeSum(1,1,n,x+1,y+1));
            }
        }
    }
    return 0;
}