enigmaavkm's blog

how to find sum up to kth element of sorted sub-array from l to r ?
By enigmaavkm, history, 7 years ago, In English

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.

  • Vote: I like it
  • +36
  • Vote: I do not like it

Comments Comments (32)
| Write comment?
»
7 years ago, # |
  Vote: I like it +30 Vote: I do not like it

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))

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I have little bit experienced with Mo's algorithms,so i am not getting how to implement it using Mo's ? Please explain.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      What specifically don't you understand?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        How to define its Block's array and queries on it.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 2   Vote: I like it +18 Vote: I do not like it

          You take all queries ans sort them with comparator 

          bool comp(pair<int,int> a, pair<int,int> b){
    if (a.F / BLOCK == b.F / BLOCK) return a.S < b.S;
    return a.F / BLOCK < b.F / BLOCK;
}

          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.

          → Reply
»
7 years ago, # |
  Vote: I like it +50 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    That can even be done in O(q*log(n)) time using wavelet tree.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +21 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    can you explain the binary search part?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Wouldn't that be log(n)3 per query?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

          → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        Thanks Got it :D.After reading this i feel like binary search can be used to solve anything :P

        → Reply
»
7 years ago, # |
  Vote: I like it +62 Vote: I do not like it

Also it can be done with a persistent segment tree in , where MAX is the maximum number in the array.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    can u pls explain how to do this as i have not used persistent segment tree before. specifically on what conditions to build. tia

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Conceptually easiest solution and best time complexity.

    → Reply
»
7 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Can you, please, share the problem link?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Also it can be done with a parallel binary search in O((N + Q) * log(N)2).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You mean, something like merge sort tree?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No,you can read about parallel binary search here.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply