0
$\begingroup$

For range queries on a subarray [L,R] , I want to find all the indices of successive maximums from left to right within O(log(R-L+1)), excluding index "L". I know using segment trees I can find the single maximum in given time limit.

Example if [L,R] is 20 3 10 5 10 7 6 7 5 7 5 -> the bold ones are the answers

Note

  1. that 20 is excluded but the first maximum i.e 10 has to be lesser than 20
  2. In case of multiple occurrences of a particular maximum, the rightmost index must be used

Also, there is a need for updation of array elements so an online query algorithm would be helpful!

Improve this question
$\endgroup$
  • $\begingroup$ If I understand you correctly, doesn't it take O(R-L) time to list all the indices? If so, how can you hope for a log-time algorithm? $\endgroup$ – Pål GD Jul 9 '20 at 10:46
  • $\begingroup$ In case I have misunderstood something, have you looked into segment trees? See also the Wikipedia article Segment tree. $\endgroup$ – Pål GD Jul 9 '20 at 10:48
  • $\begingroup$ John, what operation are you required to implement (or use) on the data structure? $\endgroup$ – nir shahar Jul 9 '20 at 12:44
  • $\begingroup$ I'm required to add up all the values of these successive maximums. eg. 10+7 =17 $\endgroup$ – john wick Jul 9 '20 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.