Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

tanvir_cse's blog

nth minimum number
By tanvir_cse, history, 10 years ago, In English

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

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

»
10 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

why not use persistent segment tree?

→ Reply