### luckytoilet's blog

By luckytoilet, 3 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"?

 » 3 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.
•  » » 3 years ago, # ^ |   +6 with using fractional cascading it can be reduced by nlogn fractional cascading
 » 3 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.
•  » » 10 months ago, # ^ |   0 What if there are updates ?
•  » » » 10 months ago, # ^ |   0 You can do it in with segment tree which keeps the full interval in each vertex then.
•  » » » » 10 months 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 ?
 » 3 years ago, # |   +6 u can also solve this problem using SQRT decomposition :)
 » 12 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.
•  » » 10 months ago, # ^ |   +16 How ?