Hello there, I am struggling to understand a piece of code. The question is Circular RMQ. My solution 1xLDk5 - Online C++0x Compiler & Debugging Tool - Ideone.com here gives WA. But just modifying the update and query function as the code below gives correct answer. Please anyone tell me what is happening here ?
void update(ll node, ll low,ll high,ll l, ll r, ll val){
if(marked[node]!=0){
tree[node] += marked[node];
if(low !=high){
marked[2*node] += marked[node];
marked[2*node+1] += marked[node];
}
marked[node] = 0;
}
if(r<l) return;
if(low ==l && high == r){
tree[node]+= val;
if(low != high){
marked[2*node] += val;
marked[2*node+1] += val;
}
return;
}
ll mid = (low+high)/2;
update(2*node,low,mid,l,min(r,mid),val);
update(2*node+1,mid+1,high,max(mid+1,l),r,val);
tree[node] = min(tree[2*node],tree[2*node+1]);
}
ll query(ll node, ll low, ll high, ll l, ll r){
if(marked[node]){
tree[node] += marked[node];
if(low !=high){
marked[2*node] += marked[node];
marked[2*node+1] += marked[node];
}
marked[node] = 0;
}
if(r<l) return inf;
if(low == l && high == r){
return tree[node];
}
ll mid = (low+high)/2;
ll left = query(2*node,low,mid,l,min(r,mid));
ll right = query(2*node+1,mid+1,high,max(mid+1,l),r);
return min(left,right);
}