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?