# Need help with Segment tree implementation

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;
}``````

havent run your code, but i think lazy should be initialized to 0 before every update or query. i may be wrong… will check code later and confirm

i have faced all the problem u r facing and after that i tried very hard and now i am to good in segment tree and for other help i have created repository on github pls check that first https://github.com/gyanendrasinghpanwar/persistent-segment-tree

error is here:

you are taking in array v[],but in build function you are using a[] array.

I am not sure as you can be onto something which i can’t fathom at the moment but don’t you think if we initialized lazy with 0 before every query/update it will lose the previous data that lazy tree is supposed to carry ?

when u will get that u will easily sort out on ur own but still i will add ur code with correction on my github

AND PLS UPVOTE ME I WAS UNABLE TO ASK QUESTION ON CODECHEF