void query(int w, int s, int e, int node)
{
if (s==e)
{
tree[node] -= w;
prpogateNewMax(node);
return;
}
mid = (s+e)>>1;
if (tree[(node<<1)+1] > = w) query(w, s, mid, (node<<1)+1);
else query(w, mid+1, e, (node<<1)+2);
}
void prpogateNewMax(int node)
{
if (node == 0) return;
int par = (node-1)>>1;
int a = tree[(par<<1)+1];
int b = tree[(par<<1)+2];
tree[par] = a > b ? a : b;
prpogateNewMax(par);
}
Now I think everything is clear. For a single query we have traverse from
root to leaf than leaf to root. total 2*log(n); So finally for n queries
order will be O(n*logn);
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
