tyristik's blog

Is sublinear RMQ query time with point updates in O(1) possible?
By tyristik, history, 3 days ago, In English

The dynamic RMQ problem goes as follows:

Given an array of integers $$$a$$$ of length $$$n$$$ and $$$q$$$ queries of $$$2$$$ types:

  1. $$$l\ r$$$ — find the minimum on $$$a[l..r]$$$
  2. $$$i\ x$$$ — make $$$a_i = x$$$

If the number of updates $$$\gt \gt$$$ the number of queries (which may occur in MO algorithm for example, where we can have $$$O(n)$$$ min queries and $$$O(n\sqrt n) $$$ updates), what is the most efficient way to solve the problem?

We obviously need smth faster than $$$O(\log(n) )$$$ per update (which is achievable with a ton of ways), like $$$O(1)$$$ or maybe $$$O(\log{\log{n} }) $$$.

I though about it for a while but wasn't able to come up even with sublinear solution for querying min while preserving $$$O(1)$$$ update time.

  • Vote: I like it
  • +74
  • Vote: I do not like it

»
3 days ago, # |
  Vote: I like it -48 Vote: I do not like it

not most effective for MO algorithm

split in blocks of length log log n, store minimum in each

to update you naively recalculate minimum in the block

then you can answer in O(n / log log n), update in O(log log n)

you are welcome

you can also do O(log log log n) by the way

O(1) I dont know though

→ Reply
»
2 days ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I came up with one solution that works in $$$O(n * \sqrt{n})$$$, but it's pretty unsatisfying, since it requires offline queries, and sorting all queries of second type by $$$x$$$ in $$$O(n * \sqrt{n})$$$ (for example it is possible if $$$x$$$ is in range $$$[1, n]$$$).

Solution

Hopefully that's good enough.

→ Reply
  • »
    »
    111 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I see. But in practice bottom-up segtree worked actually fine. Especially with optimization of not going further up if minimum in vertex didn't change.

    → Reply
»
2 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Think this is supposed to translate to "you can't beat amortized O(log)".

→ Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    MIHAI PATRASCU MENTIONED 🇷🇴 🇷🇴 🇷🇴 🇷🇴 🇷🇴 🇷🇴 FIRST EVER COMMUNICATION PROBLEM IN IOI 🇷🇴 🇷🇴 🇷🇴 🇷🇴 🇷🇴 🇷🇴 WHAT EVEN IS LR BINARY SEARCH 🇷🇴 🇷🇴 🇷🇴 🇷🇴 🇷🇴

    → Reply
»
2 days ago, # |
  Vote: I like it -33 Vote: I do not like it

I think for the Mo problem you can use the second idea listed here (i.e. replace the segment tree which admits online O(log)/O(log) for sqrt decomposition which admits O(1)/O(sqrt) update/query)

→ Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    But how will you do updates in $$$O(1)$$$? You need to recalculate minimum on whole block.

    → Reply
    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      Oh true. Who would've thought thinking before speaking is a good idea.

      → Reply
»
38 hours ago, # |
  Vote: I like it +17 Vote: I do not like it

where is chinese comment explaining how to do it

→ Reply