I am trying to implement sum over a given range problem using seg tree but I seem to be struck here as my code is not working properly. Please help me in correcting this code and enlightening me about where am I going wrong ?
#include<bits/stdc++.h>
using namespace std;
#define size 4000
int a[size] , seg[4*size] , lazy[4*size];
void build(int pos , int low , int high){
if(low > high)return;
if(low == high){
seg[pos] = a[low];
return;
}
int mid = (low + high)/2;
build(2*pos , low , mid);
build(2*pos+1 , mid+1, high);
seg[pos] = seg[2*pos] + seg[2*pos+1];
}
void update(int pos , int low , int high , int qlow , int qhigh , int val){
if(lazy[pos]){
seg[pos] += lazy[pos];
if(low != high){
lazy[2*pos] += lazy[pos];
lazy[2*pos+1] += lazy[pos];
}
lazy[pos] = 0;
}
if(low > high || low > qhigh || high < qlow)return;
if(low >= qlow && high<=qhigh){
seg[pos] += val;
if(low != high){
lazy[2*pos] += val;
lazy[2*pos+1] += val;
}
return;
}
int mid = (low + high)/2;
update(2*pos , low , mid , qlow , qhigh , val);
update(2*pos+1 , mid+1 , high , qlow , qhigh , val);
seg[pos] = seg[2*pos] + seg[2*pos+1];
}
int query(int pos , int low , int high , int qlow , int qhigh){
if(low > high || low > qhigh || high < qlow)return 0;
if(lazy[pos]){
seg[pos] += lazy[pos];
if(low != high){
lazy[pos*2] += lazy[pos];
lazy[pos*2+1] += lazy[pos];
}
lazy[pos] = 0;
}
if(low >= qlow && high <= qhigh)
return seg[pos];
int mid = (low + high)/2;
int q1 = query(2*pos , low , mid , qlow , qhigh);
int q2 = query(2*pos+1 , mid+1 , high , qlow , qhigh );
return q1+q2;
}
int main(){
int n , i;cin>>n;
int v[size];
for(i=0 ; i<n; i++)cin>>v[i];
build(1 , 0 , n-1);
memset(lazy , 0 , sizeof(lazy));
int q;
cin>>q;
while(q--){
int ch , l , r;
cin>>ch>>l>>r;
if(ch == 0){
cout<<query(1 , 0 , n-1 , l-1 , r-1 )<<endl;
}
else{
int val;cin>>val;
update(1 , 0 , n-1 , l-1 , r-1 , val);
}
}
return 0;
}