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

Revision en2, by 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).

Tags #segment tree, #range query

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English AryanDLuffy 2020-06-06 09:56:56 18 Tiny change: '((logn)^2)' -> '((logn)^2).' (published)
en1 English AryanDLuffy 2020-06-06 09:55:37 315 Initial revision (saved to drafts)