Range queries of the form (l,r,x)

Правка en2, от AryanDLuffy, 2020-06-06 09:56:56

Can range queries of form (l,r,x) where the answer to the query is number of values less than x in range [l,r] of a given array be solved in O(logn) time online? There are no updates. Plz describe the solution if it exists. I know of the solution by merge sort tree which solves it in O((logn)^2).

Теги #segment tree, #range query

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский AryanDLuffy 2020-06-06 09:56:56 18 Tiny change: '((logn)^2)' -> '((logn)^2).' (published)
en1 Английский AryanDLuffy 2020-06-06 09:55:37 315 Initial revision (saved to drafts)