luckytoilet's blog

By luckytoilet, 2 years ago, ,

I was looking at the editorial for Round #300 Problem F, where you needed to count how many elements in a range is greater than k. The editorial stated "online data structures for this type of query are rather involved" and proceeds to describe a solution using the simpler Binary Indexed Tree.

Is there any known data structure that can efficiently query "how many elements in this range is greater than k"?

 » 2 years ago, # |   +21 Segment Tree. In vertex we store sorted subarray using std::vector. Than, for find count of elements in segment [l, r] greater then k, we can do upper_bound in each of log(n) vertex, so complexity is O(log^2(n)) per query.
•  » » 2 years ago, # ^ |   +6 with using fractional cascading it can be reduced by nlogn fractional cascading
 » 2 years ago, # |   +8 If there is no update queries, persistent segment tree will do. per query.Also, if you solve problem in offline BIT is enough.
•  » » 7 days ago, # ^ |   0 What if there are updates ?
•  » » » 7 days ago, # ^ |   0 You can do it in with segment tree which keeps the full interval in each vertex then.
•  » » » » 7 days ago, # ^ |   0 With the segment trees ... each node will be having the range in sorted order .... but when there will be an update for an interval range ..like index 3 to index 5 have to be increased by an amount of 10 .. then whole of the segemnt trees has to updated ( just like the normal update procedure ) and again each node has to be sorted ... Would that be efficient ?
 » 2 years ago, # |   +6 u can also solve this problem using SQRT decomposition :)
 » 2 months ago, # |   0 you can also solve this problem using trie. I solved a similar problem using this approach where u need to find number of elements in range(l,r) which are <= k in each query.
•  » » 7 days ago, # ^ |   +16 How ?
•  » » » 7 days ago, # ^ |   +8 We can build a binary trie tree where at each node we store a vector containing the index of element of which that node is a part of. Something like this :``````struct trie_node { trie_node *next[3]; vector v; }; ``````For example we want to insert `arr[10] = 5` and `arr[11] = 2` in the trie. Let us consider all the elements in the array fits in 4 bits at max. So `5 = b(0101)` and `2 = b(0010)` in binary. We can build a trie like following in `O(log2(maximum arr[i]))`. Visual representation : Insert Function :``````trie_node *insert(struct trie_node *temp,int x,int mask,int ind) { if(mask==0) return temp; if(temp==NULL) { temp=new trie_node(); temp->next[0]=temp->next[1]=NULL; } temp->v.push_back(ind); if(x&(mask>>1)) temp->next[1]=insert(temp->next[1],x,mask>>1,ind); else temp->next[0]=insert(temp->next[0],x,mask>>1,ind); return temp; } ``````Now for the query portion i.e. finding number of elements greater than k in range l to r, what we can do is to count the number of elements less than or equal to k and then subtract it from total number of elements in range l to r to obtain our output.If we start traversing the binary representation of k from most significant bit to least significant we find the if ith bit of k is set then all the elements in trie with ith bit unset are less than k. So we can add the count of all indexes in the range l to r to the answer.If ith bit is unset then all elements with ith bit set are greater than k, so we ignore those elements. Following is a recursive function implementing the above idea. Count Function (<= k) :``````int cnt(struct trie_node *root,int l,int r,int x,int mask) { if(root==NULL) return 0; if(!root->next[0]&&!root->next[1]) return total(root->v); if(x&(mask>>1)) { if(root->next[0]) return total(root->next[0]->v) + cnt(root->next[1],l,r,x,mask>>1); else if(root->next[1]) return cnt(root->next[1],l,r,x,mask>>1); } else return cnt(root->next[0],l,r,x,mask>>1); } ``````Here `total(v)` counts the number of elements `>= l` && `<= r` in the given vector v. It is defined as :`upper_bound(v.begin(),v.end(),r) - lower_bound(v.begin(),v.end(),l)` Finally you calculate answer as : `r - l + 1 - cnt(root,l,r,k,(1<<30))))` assuming maximum element in array to fit in 30 bits.
•  » » » » 6 days ago, # ^ |   0 Nice explanation. Thanks.
 » 7 days ago, # |   +1 For contests, If you need a good abtraction or if you want to learn a new merge-sort tree based datastructure for certain class of problem, Check this