For finding maximum in a given range for an array , we need to construct a
seg tree of hight log(n).
So, for n queries out time complexity will be O(nlogn).
Now, if out query window size is known before hand, suppose j-i==K, how can
I reduce the complexity to (nlogK for finding an minimum for a
is J-I = K for all queries?
On Fri, Jul 1, 2011 at 4:08 PM, oppilas . jatka.oppimi...@gmail.com wrote:
For finding maximum in a given range for an array , we need to construct a
seg tree of hight log(n).
So, for n queries out time complexity will be O(nlogn).
Now, if out query window size
Sunny yes.. I want to implement RMQ solution of it in O(nlogk) not
O(nlogn).
On Fri, Jul 1, 2011 at 4:38 PM, sunny agrawal sunny816.i...@gmail.comwrote:
is J-I = K for all queries?
On Fri, Jul 1, 2011 at 4:08 PM, oppilas . jatka.oppimi...@gmail.comwrote:
For finding maximum in a given range