Problem:
We have given an array A[] of size N. Now we have given Q queries, each queries consist of three integer l,r,k where:
1<=l<=r<=N
1<=k<=(r-l+1)
1<=N,Q<=10^5
Now,we want to find out the sum upto the k element of the sorted sub-array from l to r.
For example:
N=6 and array element be 5,1,7,4,6,3 And Q=1 where l,r,k be as 2,5,3. then sub-array from index 2 to index 5 be {1,7,4,6} after sorting it becomes as {1,4,6,7} so sum upto k=3 term is equal to (1+4+6)=11 so answer is 11 .
I have tried using sorting of each sub-array and then sum, it takes Q*N*log(N) time complexity in worst case. Please help to find any better solution within time complexity less than Q*N in worst case.
You can just use Mo's algoritm link.
So you can store current elements in treap or segment tree to find sum. It will work in O(n*sqrt(n)*log(n)+q*log(n))
I have little bit experienced with Mo's algorithms,so i am not getting how to implement it using Mo's ? Please explain.
What specifically don't you understand?
How to define its Block's array and queries on it.
You take all queries ans sort them with comparator
now you have you current segment [L, R]. you take queries from sorted array. let's you current query is [cL, cR]. you must move L to cL and R to cR. so if you store elements from current range in treap, and make L++, then you need to delete a[L] from treap. if you make L-- then you need to add a[L - 1] to treap. then move R. and now you current range is same with query range and you can take sum in treap.
Also it can be done in O(q*log(n)*log(n)).
Let's build segment tree and in node you store all elements in this range in increasing order. So to answer query you can do binary search to find kth element. And then using prefix sum find sum.
That can even be done in O(q*log(n)) time using wavelet tree.
How would you handle disjoints ranges? I mean, a i-th element (i <= k) in some subrange may be the j-th element (j > k) in the whole query range.
Maybe you don't understand my solution. At first I do global binary search to find kth element in the whole query range. Then I find sum.
Would it work if all elements on the array were equal?
I think yes)
Could you explain how your solution works when the range is not equal to range of any node for segment tree
May be code will look like this :P
See the comment below
can you explain the binary search part?
Let's segment tree has two functions.
1. findcnt(l, r, val) is number of Ai(i = l..r) such that Ai ≤ val
2. findsum(l, r, val) is sum of Ai(i = l..r) such that Ai ≤ val
So if query is (l, r, k) then I find such minumum x that findcnt(l, r, x) ≥ k.
Now let's mid is middle of binary search.
If findcnt(l, r, mid) ≥ k then make the right border equal to mid, else make the left border equal to mid + 1.
Answer for query is findsum(l, r, x) - x * (findcnt(l, r, x) - k)
my code
Wouldn't that be log(n)3 per query?
We can drop one
factor by building merge sort tree with indices not with values. Then merge the binary search process with the tree query. While doing query check if answer is completely in left child, then go to left child, else search for answer in right child with 
. This will have 
complexity.
We can drop another
factor, if we use Persistent Segment tree. Then we can get 
per query.
Thanks Got it :D.After reading this i feel like binary search can be used to solve anything :P
Also it can be done with a persistent segment tree in
, where MAX is the maximum number in the array.
can u pls explain how to do this as i have not used persistent segment tree before. specifically on what conditions to build. tia
Let's have one version for every prefix of array. If you want go from prefix R to R + 1 you create new version and add 1 to position a[R + 1]. In every node of tree you store sum of elements in this range and their amount. To answer query (l, r, k) you take two vesions l - 1 and r. So you start from root. If rootr.cnt - rootl - 1.cnt = k then ans + = rootr.sum - rootl - 1.sum and break, else if left[rootr].cnt - left[rootl - 1].cnt > k then you make rootr = left[rootr] and rootl - 1 = left[rootl - 1] and continue, else ans + = left[rootr].sum - left[rootl - 1].sum, delete this elements from k k - = left[rootr].cnt - left[rootl - 1].cnt and go to the right rootr = right[rootr] rootl - 1 = right[rootl - 1] and continue.
Conceptually easiest solution and best time complexity.
Can you, please, share the problem link?
Actually, this is not any contest problem. I just implementing a problem and thought this problem
https://www.codechef.com/problems/CDZ14E
Intuitive solution to this problem !
Also it can be done with a parallel binary search in O((N + Q) * log(N)2).
You mean, something like merge sort tree?
No,you can read about parallel binary search here.
It looks to me that merge sort tree does logMAXVAL( logn if compressed ) binary searches on segments of size n. From that, I said that there are logn paths for binary search, hence parallel binary search. Although I see it's not completely parallel, as the search path depend on success/failure of the previous binary search.
Can you explain your solution so we can understand better. No need for verbose explanation, just give the basic idea.
Firstly try to find the Kth element of the sorted sub-array from L to R with parallel binary search, remaining part of solution is too easy.