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

Time complexity of Sparse table query
Автор Siriuslight, история, 7 лет назад, По-английски

I am little confused on time complexity of a query in sparse table. I got conflicting answers from two sources. On hackerearth O(logn) (link) is mentioned and on geeksforgeeks O(1) (link) is mentioned.

Can anyone tell me the correct time complexity?

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

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

If your query will not be affected with overlapped ranges like RMQ (i.e RMQ in range [1, 10] is the same of min( RMQ[1, 6], RMQ[4, 10]) ), then you can solve it in O(1). But if your query will be affected with overlapped ranges like Range Sum Query, then you have to solve it in O(log(n)) as mentioned in hackerearth like.

→ Ответить