Horrible queries (With Lazy Propagation)

                                    http://www.spoj.com/problems/HORRIBLE/
                     

HORRIBLE - Horrible Queries

If the node is lazy. firstly ,it is needed to update that node.
and after that making their childs as lazy (if they have childs en!=st).





#include<bits/stdc++.h>

using namespace std;
long long int tre[1000000],a[1000000],lazy[1000000];

long long int query(long long int node,long long int st,long long int en,long long int fs,long long int fe)
  {
  //     cout<<st<<" "<<en<<endl;
  if(lazy[node]!=0)
  {
      tre[node]+=(en-st+1)*lazy[node];
      if(st!=en)
      {
          lazy[2*node]+=lazy[node];
          lazy[2*node+1]+=lazy[node];
      }
      lazy[node]=0;
  }

  if(fe<st || fs>en || fs>fe)
    return 0;

 if(fs<=st && fe>=en)
 {
    //  cout<<"ret "<<tre[node]<<endl;
     return tre[node];

 }

 else
 {
     long long int q1=query(2*node,st,(st+en)/2,fs,fe);
     long long int q2=query(1+2*node,1+(st+en)/2,en,fs,fe) ;
  return q1+q2;
  }
}







void update(long long int node,long long int st,long long int en,long long int fs,long long int fe,long long int sum)
{

  if(lazy[node]!=0)                       /// this is lazy ,so it's needed to be update
  {
    tre[node]+=(en-st+1)*lazy[node];              ///update occured
    if(st!=en)
    {
        lazy[2*node]+=lazy[node];     /// it made its child lazy
        lazy[2*node+1]+=lazy[node];  /// it made its child lazy
    }
    lazy[node]=0;
  }

  if(fe<st || fs>en || fs>fe)
    return ;

 //if(st==en)               /// update will occur at the  leaf
   // tre[node]+=sum;

   if(st>=fs && en<=fe)   /// it is lazy aproach no need to update at leaf,,, just make ur childs lazy with sum value
   {
       tre[node]+=(en-st+1)*sum;
       if(st!=en)
       {
           lazy[2*node]+=sum;
           lazy[2*node+1]+=sum;
       }
   }
    else
    {
         update(2*node,st,(st+en)/2,fs,fe,sum);
         update(2*node+1,1+(st+en)/2,en,fs,fe,sum);
         tre[node]=tre[2*node]+tre[2*node+1];
    }
}






int main()
{
 int t;
 cin>>t;

 while(t--)
 {

  for(long long int i=0;i<1000000;i++){a[i]=0; tre[i]=0; lazy[i]=0;}

   long long int n,i,ty,sum,q,l,r;;
   cin>>n;

    for(i=1;i<=2*n;i++)
    tre[i]=0;

   // build_tree(1,0,n-1);                   /// tree is to be built and minimum given to 1th index

     // for(i=1;i<2*n;i++)
      //cout<<tre[i]<<" ";
     cin>>q;
    for(i=0;i<q;i++)
    {
     cin>>ty;
     if(ty==1)
     {
     cin>>l>>r;
     l--; r--;
     cout<<query(1,0,n-1,l,r)<<endl; /// starting ur query , start looking ur range (l,r) from the 1st node of tree whose range is(0,n-1)
     }
     else
     {
       cin>>l>>r>>sum;
       l--; r--;
       update(1,0,n-1,l,r,sum);
        //for(i=1;i<2*n;i++)
        //cout<<tre[i]<<" ";
     }
    }
 }
return 0;
}