sorry, above mail is addressed to Anshu. :P
On Mon, May 16, 2011 at 10:08 PM, Akshata Sharma
<akshatasharm...@gmail.com>wrote:
> @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 <anshumishra6...@gmail.com> 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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
