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

nth minimum number
Автор tanvir_cse, история, 8 лет назад, По-английски

given an array arr and for each query given l,r,k to ditermine kth minimum number in the range[l,r]. how to determine kth minimum element in a given range by treap thanx in advance

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

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

I don't know about using treap to solve this problem, but user ffao has an awesome guide on how to solve it using a "reverse mergesort" technique: https://www.quora.com/How-can-you-build-a-data-structure-on-an-array-that-returns-kth-order-statistics-on-subarrays-in-logarithmic-time/answer/Fernando-Fonseca-2

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

why not use persistent segment tree?

→ Ответить