harvester's blog

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

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.

 
 
 
 
  • Vote: I like it  
  • -5
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Merge sort segment tree would process queries in log(n). You can easily find further information about it.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    TooNewbie How is Merge sort segment tree Query in logN? Isn't it log^2N? Thanks.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Yes. My bad, it's log^2(n).

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Can you link some material regarding logN per query with fractional cascading ? I am unable to find. Thank you.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          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   Vote: I like it +3 Vote: I do not like it

Persistent segment tree — O(N * logN)
Persistence Made Simple — Tutorial Persistent segment trees

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    I think it's , or you mean .

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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   Vote: I like it +9 Vote: I do not like it

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, # ^ |
      Vote: I like it +11 Vote: I do not like it

    You can also use BITs to decrease the constant factor of this solution.