I’m confused… Why would the complexity have a factor of logAi in the “Bonus” part. I can only think of a O(q*log^3 n) solution. Binary search over the array and find the value that has k-1 smaller numbers in O(log^2 n).
Also, would appreciate if you could upvote me. Need karma points
Thanks!
For the bonus part, consider a query(L,R,X), and X=R-L+1, which means that you need to find out the maximum number from the range L to R. According to your solution, we can binary search on Ai, and find out which number gives number of numbers <= Ai to be X. But how will you keep a track of Ais which are present in the range [L,R] of the original array A? This is needed because for the case where you need to find the maximum in a range [L,R], any number Y lying between the maximum number from [L,R] and the next maximum in the array A will also yield X as the answer to the query(L,R,Y).
We can achieve much better. First, we compress the array in order to contain only values in range [0,N). We keep a table to associate a compressed value to the original one in O(1) and associate a normal value to his lower_bound in compressed range in O(logN). This take us so far NlogN. Then we build a Persistent Segment Tree, where for every time i we have stored the frequencies of each value in the array with index smaller or equal to i, and every node store the sum of the two sons. Overall is NlogN preprocessing.
Every time we want to know how many integers there are in range [l,r] smaller than k, we do as follows:
first we replace k with the compressed value of the greater original value smaller than k. //logN
We query the Persistent Segmentent Tree in the interval [0,k], assuming that the value written in each node is the one of the tree® - tree(l-1).
In the end we use NlogN space and time complexity for preprocessing, and each query take logN. But we can do a lot of amazing other stuff, for example, being asked about the k-th smallest value in range [l,r], and answer in logN as well.
yes, you are correct too. thats one way to see it. if you binary search over the array it will come out to be O(qlog^3 n). but if you binary search over the a[i] value then it comes out to be O(qlog^2 n*log ai).
i think you aren’t clear about binary search, we will binary search for the smallest number that satisfies the above condition i.e. for query(L,R,X), and X=R-L+1.find out the smallest number which gives number of numbers <= Ai to be X. Theres no need to track its presence in array.
@mayank12559, I tried to optimise your solution by making the binary serach iterative as well, but no sucess. May be the time limits of the problem are strict for java for passing with O(log^2n) approach. Also, only 4 solutions in java for this problem till date. May be you can try with C++.
Thanks for the reply. I will try to write the same in c++. Java solution should also get accepted though, as c++ solutions are getting accepted with same complexity. There should not be any discrimination among languages.
Why do you think log2(10^5) * 10^5 vectors are required? vectors should be equal to number N+N/2+N/4+N/8…(i.e number of nodes in segtree) Which is 2N but we require a number which is multiple of 2 and greater than 2N. So to be on safe side we usually take 4*N nodes in segtree.
maybe. After all, the only important things -after understand segment tree in its pointer implementation- are:
-In each update, at most logN node change
-In each update, create a new version of all nodes changed
I think your code counts no. of elements smaller than or equal to k. To find no. of elements smaller than k, lower_bound must be used instead of upper_bound in the code for query function.