Introduction
This blog will discuss the problem of evaluating the queries to find the number of elements less than or equal to a given number in a given subarray.
In this problem, we will be given an array of integers containing ‘N’ elements, and ‘q’ number of queries. Each query is of the form {X, L, R} and for each query, we have to find the number of elements less than or equal to ‘X’ in subarray [L, R] of the given array.
Let's take an example to understand the problem:
Assume the given array and number of queries are:
arr = {2, 4, 3, 6, 9}
q = 3
And the queries are: {{2, 0, 3}, {7, 0, 4}, {3, 0, 2}}
The given queries will be evaluated as follows:
Query 1: {2, 0, 3} = Number of elements less than or equal to 2 in the subarray {2, 4, 3, 6} = 1
Query 1: {7, 0, 4} = Number of elements less than or equal to 7 in the subarray {2, 4, 3, 6, 9} = 4
Query 1: {3, 0, 2} = Number of elements less than or equal to 3 in the subarray {2, 4, 3} = 2
Now that we understand the problem let's discuss the approach to solve it in the next section.
Solution Approach
This section will discuss the approach to find the number of elements less than or equal to a given number in a given subarray. A simple approach is to traverse the given subarray in each query and count the number of elements less than or equal to the given value of ‘X’.
The efficient approach is to use a Binary Indexed tree. We can use a binary indexed tree “bit” array to store the number of elements less than or equal to ‘x’ in arr[0……i] for each value of ‘i’ and then for a query {x, L, R}, calculate the number of elements less than equal to ‘x’ in the range [L, R] as the number of elements less than equal to ‘x’ in the range [0, R] minus the number of elements less than or equal to ‘x’ in the range [0, L1].
Algorithm 
Step 1. First, the main function. Inside the main function, create an array ‘arr’ to store the given array and a twodimensional vector to store queries of the form {x, L, R}. Then call the function “evaluateQueries()” to find the number of elements less than or equal to a given number in a given subarray for each query.
Step 2. Next, create the function “evaluateQueries()” to find the number of elements less than or equal to a given number in a given subarray for each query. It takes following input parameters:
 arr: Given array of elements
 queries: A 2dimensional vector storing the queries of thr form {x, L, R}
 n: Number of elements in the given array
 q: Number of queries
Step 3. Inside the function “evaluateQueries()”, create “bit” array of size ‘n’ and store all its elements as ‘0’ initially. Sort the array ‘arr’ and the ‘queries’ vector accoriding to increasing order of ‘x’. Before sorting the ‘queries’ vector, store the original index of each query.
Step 4. Now, for each query traverse the array till the array elements are less than equal to ‘x’ and update ‘bit’ array. Then store ans for each query as number of elements less than equal to ‘x’ in range [0, R] minus number of elements less than or equal to ‘x’ in range [0, L1].
Step 5. Finally, write the helper functions “update()” to store the number of elements less than or equal to a given number for each index and “query()” to find the number of elements less than or equal to a given number in a given subarray.
C++ code:

Output

Also read, Euclid GCD Algorithm
Algorithm Complexity:
Time Complexity: O(Q * log(N))
In the function “evaluateQueries()” for evaluating the queries to find the number of elements less than or equal to a given number in a given subarray, “update()” and “query()” functions having time complexity of log(N), are called for each query. So, the overall time complexity is O(Q * log(N)), where ‘Q’ and 'N' are the number of queries and the number of elements in the array respectively.
Space Complexity: O(N)
In the function “evaluateQueries()” for evaluating the queries to find the number of elements less than or equal to a given number in a given subarray, we have created a vector 'bit' for Binary indexed tree, so the space complexity is O(N), where 'N' is the number of elements in the given array.
Check out this problem  Count Inversions