[Help needed] How many integers in a sub array which are less than a given value?

Revision en2, by shahidul_brur, 2017-06-08 14:59:49

Problem:

Given an array of n integers and q queries of the form: Q(L, R, x). For each query Q(L, R, x), you have to say "How many integers in the range L to R(inclusive) which are less than x".

There is no update operation.

Constraints:

  • 1 ≤ n ≤ 1900000
  • 1 ≤ q ≤ 105

If I use Square Root Decomposition, complexity will be O(q * sqrt(n) * logn), which is not so good for this constraints, I think.

Can you please suggest any better solution for this problem ?

Thanks in advance.

Tags #data structure, sqrt_decomposition, segment tree, range query, array

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English shahidul_brur 2017-06-08 20:14:26 355
en2 English shahidul_brur 2017-06-08 14:59:49 60
en1 English shahidul_brur 2017-06-08 14:57:38 573 Initial revision (published)