# Lower bound on online range minimum query with element value modification

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?