Number of elements less than or equal to current number in a given range .

Revision en1, by atlasworld, 2019-02-12 23:37:52

You , are given an array of n elements and q queries . Both n and q can range upto 10^5 , and 1<=a[i] <= 10^9.

how to find / count all the elements less than a given element in each query .

Example: index 1 based

a[] = {5 , 3 , 2 , 2 , 3 , 1 , 2 , 9 , 10 , 2 }

q1 = 5 9 5

ans = 3 { 3 , 1 , 2}

q2 = 1 4 2

ans = 2 {2 , 2 }

The problem gives a feel of segment tree , but how to solve it using ST ?

any idea.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English atlasworld 2019-02-12 23:40:21 2
en4 English atlasworld 2019-02-12 23:39:29 121
en3 English atlasworld 2019-02-12 23:38:33 8
en2 English atlasworld 2019-02-12 23:38:13 36
en1 English atlasworld 2019-02-12 23:37:52 523 Initial revision (published)