1
$\begingroup$

I was wondering if the following problem can be solved in asymptotically better time than$ \ O(n \log n)$.

Suppose you have an array of integers $a_1,a_2,a_3,\ldots,a_i,\ldots,a_n$ where initially for all $i$,$ \ a_i = \mathrm{INF}$.

Now, we will iterate over every element starting from $i = 1$ to $i = n$ and perform two operations.

  1. Update the element at index $i$, $a_i = v$.

  2. Answer a query of the form $\min$ in range $[l, i]$. This should return the minimum value in the range from $l$ to $i$ inclusive.

Of course, we can solve this problem using a Segment Tree where each node stores the minimum in the respective range. This data structure allows us to carry out point updates in $O(\log n)$ time, and answer range queries in $O(\log n)$ time as well. This leads to a total complexity of $O(n\log n)$ for this problem.

I know that RMQ has been studied deeply and can be done in constant time for immutable data with some preprocessing. However, in this case we are doing updates.

Is this the best we can do? Is $O(n\log n)$ a lower bound on the problem?

Improve this question
$\endgroup$
9
  • $\begingroup$ What is $v$ and what is $l$? Are they parameters at each step? If so, it sounds like you want a dynamic data structure that supports two operations: Add(x) and Min(k), where Min(k) returns the smallest of the k elements most recently added. Am I interpreting your problem correctly? $\endgroup$
    – Zach Langley
    Mar 10, 2020 at 21:41
  • $\begingroup$ Yes, that is correct. I had not looked at the problem that way. But I guess it is essentially the same. $\endgroup$
    – JhonRM
    Mar 10, 2020 at 21:43
  • $\begingroup$ @JhonRayo99, I don't think it's the same problem. From your description it seems that you want to be able to answer range queries from any arbitrary range. If you only care about the minimum among "the most recent points" the you could use an heap to get a complexity of $O(n \log k)$, where $k$ is the number of most recent points you care about. $\endgroup$
    – Steven
    Mar 12, 2020 at 22:17
  • $\begingroup$ @Steven: I disagree that "from [the] description it seems that you want to be able to answer range queries from any arbitrary range" -- the range being queried in step $i$ is always some range with endpoint $i$ (and some starting point, $l$). $\endgroup$
    – j_random_hacker
    Mar 13, 2020 at 0:45
  • $\begingroup$ You must be looking for an online solution, right? Otherwise you could just perform all $n$ updates, do the preprocessing required for constant-time RMQ queries, and then do $n$ constant-time RMQ queries, for a total of $O(n)$ time. $\endgroup$
    – j_random_hacker
    Mar 13, 2020 at 0:47

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.