I am solving http://www.spoj.com/problems/HORRIBLE/ ,which is crashing on entering the first query.I am yet to implement the add function,but update function is not working .
long long int a[10000000];
long long int segtree[450000];
long long int lazy[450000];
void updatetree(int low,int high,int value,int qlow,int qhigh,int pos);
int main()
{
ios::sync_with_stdio(false);
int t,b;
long long int n,c,p,q,v,i;
cin>>t;
while(t--)
{
// memset(lazy,0,sizeof(lazy));
cin>>n>>c;
for(i=0;i<450000;i++)
{
lazy[i]=0;
segtree[i]=0;
}
for(i=0;i<n;i++)
a[i]=0;
for(i=0;i<c;i++)
{
cin>>b;
if(b==0)
{
cin>>p>>q>>v;
updatetree(0,n-1,v,p,q,0);
}
/* else
{
cin>>p>>q;
addtree(p,q);
}*/
}
}
return 0;
}
void updatetree(int low,int high,int value,int qlow,int qhigh,int pos)
{
if(lazy[pos]!=0)
{
segtree[pos]+=lazy[pos];
if(low!=high)
{
lazy[2*pos+1]+=lazy[pos];
lazy[2*pos+2]+=lazy[pos];
}
lazy[pos]=0;
}
if(qlow<=low&&qhigh>=high)
{
segtree[pos]+=value;
if(low!=high)
{
lazy[2*pos+1]+=value;
lazy[2*pos+2]+=value;
}
return ;
}
//if partial overlaps
int mid;
mid=(low+high)/2;
updatetree(low,mid,value,qlow,qhigh,2*pos+1);
updatetree(mid+1,high,value,qlow,qhigh,2+pos+2);
segtree[pos]=min(segtree[2*pos+1],segtree[2*pos+2]);
}
you did not set termination condition in update function what about when high is less than qless and less is greater than qhigh means “high” and “low” may cross query limit.
so set condition just above if(qlow<=low&&qhigh>=high) this(your second if statement)
condition is if(high < qlow||less > qhigh) return;
if you have any doubt then you can take look of any other lazy propa. example
or ask here
Well I modified it but it is still crashing,I also modified the calling of updatetree function to
updatetree(0,n-1,v,p-1,q-1,0);
as it was also a bug.But it is still after crashing entering the first value.
There may be some memory issue. You are using an array of size 10^7 of 64 bits data type. Further, if your indices for update varies from 0 to say x, your segment tree should be having 3x to 4x number of nodes. So, probably, you are accessing array indices out of bounds in segtree[] and lazy[].
here is your code http://ideone.com/XvXiZ4 i have made some correction and a suggestion about constant argument passing well i have not much idea about cpp i something is wrong you can say
well for n=8 there is no out of bounds in segtree and lazy and also you are not using your array at all. so do correction in your code and try out.maximum value of n is 10^5 so 410^5 is enough for segment tree. also you have taken it 4510^4 which is much sufficient. for any memory issue remove the array keep only seg. and lazy.
Hi, artist
I have gone through your latest code http://ideone.com/z2MHvN .It seems there is a major bug in these lines “segtree[pos] += lazy[pos]” and “segtree[pos] += value” . It doesn’t store the value from ranges and so it only works when there is single child.Try to prove the correctness of these lines you will surely get the bug. So the bug is suppose a parent has two child so parent sum will be sum of two children but you are only updating with single child’s value so you have to add it two times. So to generalize the concept for higher nodes in tree “segtree[pos] += lazy[pos] * (high-low+1)” and “segtree[pos] += value * (high-low+1)”, till then Happy Coding !!
your termination condition is not correct it may leads WA because there are some nodes which require updation so shift this condition to just above of third if statement(current position) and you are missing a concept that’s why getting WA because in each node you are storing some value which is to be added to each array element under that node but you are simply returning that value , in question they asking for some of all element not the value which is to be added to single element hence for making correction you need to multiply by number of array element under that node –
means-segtree[pos]+=lazy[pos] * (high-low+1) which will be sum , it seems like you are following a code which is for finding the minimum value given in range thats why you are taking segmtree=min(left,right) do it segtree=left+right.
