По техническим причинам тестирование временно остановлено. Разбираемся, прогнозов пока нет. Приносим извинения за сбой. ×

Блог пользователя Gaajvi

RMQ
Автор Gaajvi, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

no

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

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.

→ Ответить