Is there a known lower bound to the online Range Minimum Query (RMQ) problem with value modifications (given the array we perform online RMQ on, support dynamically modifying the values of a given element in the array)?

The Wikipedia page on range minimum queries cites the $O(n)$ preprocessing, $O(1)$ query-time algorithm for performing online RMQs on an immutable array by Farach-Colton and Bender, which they prove to be optimal.

There's also a folklore algorithm on using segment trees (or tournament trees in formal literature, see 1): https://cp-algorithms.com/data_structures/segment_tree.html. They support query, single-element value modifications, and range modifications in $O(\log n)$, while taking $O(n)$ preprocessing time.

I'm curious if there are any literature mentioning a lower bound to online RMQ with single-element value modifications and range modifications? Alternatively, are there any known efficient algorithms if we extend this problem to add element insertion/deletion?

To formalize the problem statement a bit, is there a known optimal algorithm supporting the following online queries on an array $A$ with length $n$:

$RMQ(l,r)$ return the range minimum in A[l...r]

$Add(i,x)$ Add $x$ to $A[i]$

$AddRange(l,r,x)$ add $x$ to A[l..r] inclusive

If there's no known optimal algorithm, is there a lower bound?


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.