@Anuj: I have a doubt. I am not getting how to update all the nodes up the leaf node which we found in the query for our value. The biggest capacity bin for all the above nodes will change once we modify the leaf value. How to propagate this upwards? After each query, do we again need to run the update operation on all array values after modifying the array index where we found the bin for our query?
On Mon, May 16, 2011 at 6:32 PM, anshu <[email protected]> wrote: > we can use BIT or segment trees. > > algorithm using segment tree > > 1. intialize all node wid zeros > 2. read the array element according their index update the node value. > > void update(int s, int e, int k, int node) > { > if (tree[node] < ar[k]) tree[node] = ar[k]; > if (s==e) return; > mid = (s+e)>> 1; > if (k <= mid) update(s, mid, k, (node<<1)+1); > else update(mid+1, e, k, (node<<1)+2); > } > > 3. now ur query part start > if left nodes value greater or equals to given value V then > goto left node otherwise goto right node as soon as you reach the leaf > node that will be your first fit bin and subtract value v from leaf > node. and accordingly update value from leaf to root. > > if the algorithm is not clear. you are welcome to ask. > > -- > 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. > > -- 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.
