RMQ with update without Lazy

         

RMQSQ - Range Minimum Query with update

#include<bits/stdc++.h>

using namespace std;

int tre[1000000],a[1000000];

void build_tree(int in,int st,int en)
{
 if(st>en)
        return ;
 if(st==en)
 {
     tre[in]=a[st];
     return ;
 }
 else
 {
     build_tree(2*in,st,(st+en)/2);
     build_tree(2*in+1,(st+en)/2+1,en);
     tre[in]=tre[2*in]+tre[2*in+1];
 }
}



int query(int node,int st,int en,int fs,int fe)
{
 if(fe<st || fs>en || fs>fe)
    return 0;

 if(fs<=st && fe>=en)
 {
     return tre[node];
 }
 else
 {
     return query(2*node,st,(st+en)/2,fs,fe)+query(1+2*node,1+(st+en)/2,en,fs,fe) ;
 }
}





void update(int node,int st,int en,int fs,int fe,int sum)
{
  if(fe<st || fs>en || fs>fe)
    return ;

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

 if(st!=en)
 {
         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(int i=0;i<1000000;i++){a[i]=0; tre[i]=0;}

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

    for(i=0;i<n;i++)
    a[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;
}