Is there a linear time online version of the preprocessing RMQ algorithm? That is, an algorithm that allows to update the data structure when appending additional elements at the end of the input array in O(1) (worst case or amortized) time per element (while still allowing answering arbitrary queries in constant time)?

I am aware of the sliding queries algorithm, which is online by nature but restricts the type of allowed queries. I've also seen this more general question, which is still unanswered by the time of writing this post.


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.