Gaajvi's blog

RMQ
By Gaajvi, history, 11 years ago, In English

Is there any RMQ algoritm with single element update and less time complexity than segment tree?

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

»
11 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

no

→ Reply
»
11 years ago, hide # |
 
Vote: I like it +33 Vote: I do not like it

No.

If there is, we can sort in faster than time.

Keep getting the smallest element, and update it to ∞ after.

But, it's already a well-known fact that there's no way to sort in faster than time (unless data has some special properties like counting sort or radix sort).

So, it's not possible.

→ Reply