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


  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!

  • $\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.