vasandani68's blog

Help needed in persistent segment tree problem!!!
By vasandani68, history, 9 years ago, In English

How can this problem be solved with persistent segment tree??Although there are other methods to solve this but i am interested in persistent segment tree!!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Since Ai <= 10**5, you could maintain a segment tree for each i such that it contains 1 in its jth position if arr[j] >= i.

You could form segment tree for ith index from i+1 index easily. Overall there would be total n updates. Hence O(nlogn) For querying start at root of Lth index and apply binary search to get position of kth value. O(qlogn)

AC code here

→ Reply