Search code examples
arraysrange-queryrmq

Number of elements less than 'x' in a range (l, r) both inclusive

Given an array of integers, and there is a single type of query.

Query - (L, R, X)

Find the elements less than 'X' in the range (L, R) both inclusive.

PS: all the queries are provided before hand i.e. we need to devise an offline algorithm to answer all the queries.

Solution

  • This can be done with the help of the segment tree and vectors. Maintain a vector at each node of the segment tree. While building the tree, maintain the sorted order in the vector at each node of the segment tree.

    Apply binary search to find number of Elements less than 'X' at each node of the segment tree where the query is processed.

    int count = upper_bound(v.begin(), v.end(), X) - v.begin();

    Is it possible to query number of distinct integers in a range in O(lg N)?

    Above post also describes the idea beautifully.