I_love_Saundarya's blog

How to find the count of numbers less than 'k' in a given range of array?

By I_love_Saundarya, history, 5 years ago, In English

Given multiple queries of the form : "L R k" , how to find the count of numbers less than 'k' in the range {L,R} of the array.

There are no update queries.

N=1000000.

I am not interested in the solution with a merge-sort-tree .

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Constraints?

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What is the source of this problem? Please provide a link if possible.

→ Reply
»
5 years ago, # |
← Rev. 6   Vote: I like it +11 Vote: I do not like it

If you can process the queries offline you should sort all of the values in the array. After that let's iterate over the sorted values, and add 1 to it's original position in the array using a segment tree, when all values < some k have been added, the answer for the query with that k is the sum on the query's range. Each query costs us log(n) to process thus this approach solves the problem in O(nlogn).

If you can't sort the queries offline, i sugest building a mergesort tree over the original array. In each node of the tree you will keep the values of that node's subarray sorted. Now for each query you will need to decompose the range into base nodes, and for each node binary search the number of values <k.' Building the mergesort tree takes nlogn time, and each query can be answered in logn^2, so the total time complexity is O(nlog(n)^2) This approach can also be used to handle updates. To do this you have to keep a binary search tree in each node instead of a sorted array.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    What is a mergesort tree ?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Basically divide the elements in segments like in a segment tree and for every node you keep all the values in that range sorted. When you do a query like :"number of elements between a and b from l to r" you use the same idea of segment tree to choose the segments and after that you can use binary search to count the number of elements in every range that you are interested in.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      I just wrote this code for a merge sort tree that support the query that you wanted.

      #include<bits/stdc++.h>
using namespace std;
template <class t> class MergeSortTree{
	public:
		int _l, _r, _m;
		vector<t> v;
		MergeSortTree *left, *right;
		MergeSortTree(int l, int r, vector<t> &e){
			_l=l, _r=r, _m=(l+r)/2, v[0]=e[l];
			v.resize(r-l+1);
			if(l==r)	left=right=nullptr;
			else{
				left=new MergeSortTree(_l,_m, e);
				right=new MergeSortTree(_m+1,_r, e);
				merge(left->v.begin(), left->v.end(), right->v.begin(), right->v.end(), v.begin());
			}
		}
		int count(int l, int r, t a, t b){ //Number of x -> a<=x<=b and x is between l and r
			if(l>_r || r<_l) return 0;
			if(_l>=l && _r<=r)	return upper_bound(v.begin(), v.end(), b)-lower_bound(v.begin(), v.end(), a);
			return left->count(l,r,a,b)+right->count(l,r,a,b);
		}
};
int main(){
	vector<int> v={1,5,2,7,4,1};
	MergeSortTree<int> mt(0,v.size()-1,v);
	cout<<mt.count(0,v.size()-1,0,7);
}

      Using algorithm's functions the code, as you can see, is really short.

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can use policy based data structure to solve this question (ordered_set) in O(N*logN).

You can refer to this link to look at this data structure. https://codeforces.com/blog/entry/11080

You can also solve it using SQRT Decomposition but you need to be careful about the time limit.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If you really wanna get to it... you can turn each element into a point (i, a[i]) and use an implicit 2d segment tree to query for points in the region where x is [l, r] and y is [k, infinity). O(n log^2 n)

Merge sort tree has same time complexity and MUCH better constant factor

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We can solve this problem Offline. First, sort the queries in increasing order and the values of the array as {value,index}. For each query ,using a data structure which can do sums and update operations (eg segment tree or bit), set to one the all the indices which have value < K of the current query and >= K of the previous query .As you have done this for previous queries the sum query will take into account all values < K.the answer of i'th query is sum(l,r) after performing updates. Here's my submission for a similar problem.

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Wavelet tree can solve online version of this problem in O(n*log(maxA)) and offline version in O(n*log(n)) (using compression).
Useful links:
Errichto's wavelet tree tutorial on YouTube
Codeforces blog with implementation

→ Reply