### harvester's blog

By harvester, history, 5 weeks ago, translation, ,

We are given an array of size N with numbers 1 <= Ai <= N(not always distinct).

There are N queries (L, R, K). For each query we need to print amount of Ai <= K, L <= i <= R. N <= 2e5

I know how to solve this task using Mo's Algorithm and Segment Tree in O(N * sqrt(N) * log2(N)). Is there a faster solution?

This is the original task, I know, probably there is an easier solution to it, but I want to try to solve it this way.

•
• -5
•

 » 5 weeks ago, # |   0 Merge sort segment tree would process queries in log(n). You can easily find further information about it.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 TooNewbie How is Merge sort segment tree Query in logN? Isn't it log^2N? Thanks.
•  » » » 5 weeks ago, # ^ |   +9 Yes. My bad, it's log^2(n).
•  » » » 5 weeks ago, # ^ |   +4 you can improve it to logN per query with fractional cascading, but somehow it doesn't result in better running times. Wavelet tree is another option, and it's easy to implement
•  » » » » 5 weeks ago, # ^ |   +3 Can you link some material regarding logN per query with fractional cascading ? I am unable to find. Thank you.
•  » » » » » 5 weeks ago, # ^ |   +11 suppose you want to merge 2 sorted arrays a and b into c. For each x in c, store triplet (x, first i such that a[i]>=x, first j such that b[j]>=x). So, when answering queries, you will need only 1 binary search at the top level, and all other binary searches will be replaced with these O(1) transitions.
 » 5 weeks ago, # | ← Rev. 6 →   +3 Persistent segment tree — O(N * logN)Persistence Made Simple — Tutorial Persistent segment trees
•  » » 5 weeks ago, # ^ |   +36 I think it's , or you mean .
•  » » » 5 weeks ago, # ^ |   +3 I meant base 2. Updated it to logN.At first, I wrote O(N  *  log2N  *  log2N), later on, converted it into O(N  *   log2N)
 » 5 weeks ago, # | ← Rev. 2 →   +9 One simple soln in O(N * log2(N)) is using segment trees. Lets have segment tree which has two operations.1. Update some position(x) value to 1(initially all are 0).2. Find the number of 1s in some range [l,r].Then, sort the queries in order of Ai. Before Ai query, make updates at position whose value is less than or equal to Ai. And then 2nd operation gives us the answer.
•  » » 5 weeks ago, # ^ |   +11 You can also use BITs to decrease the constant factor of this solution.