shahidul_brur's blog

[Help needed] How many integers in a sub array which are less than a given value?
By shahidul_brur, history, 8 years ago, In English

Problem:

Given an array of n integers and q queries of the form: Q(L, R, x). For each query Q(L, R, x), you have to say "How many integers in the range L to R(inclusive) which are less than x".

There is no update operation.

Constraints:

  • 1 ≤ n ≤ 1900000
  • 1 ≤ q ≤ 105

I know two ways:

  1. Using SQRT decompostion: Partition the array in SQRT(n) blocks and Sort each block. Then for each query binary search(lower bound or upper bound) x in each block. If I use Square Root Decomposition, complexity will be O(q * sqrt(n) * logn), which is not so good for this constraints, I think.

  2. Using segment tree: Store the sorted list of numbers in each node in the segment tree. Then for each query, binary search x at each required node.

Can you please suggest any better solution for this problem ?

Thanks in advance.

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

Comments Comments (24)
| Write comment?
»
8 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

You can make a segment tree, where each node is a ordered vector with the elements from l to r, then the search will be O(log^2)

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

    If the left child contains: 1, 3, 5 and right child contains: 2, 4, 6, then the node will contains: 1, 2, 3, 4, 5, 6 ?

    What will be the complexity of building the segment tree ?

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

      The complexity it will be O(Nlog^2) to construction, and O(NlogN) to memory. The depth of the segment tree will at most log(N), each level will contain at most N elements The first level contain N elements, the second contain two nodes of N/2 elements, the third contain four nodes of N/4 elements, the level logN contain N nodes of 1 element

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

        by the way, shouldn't the complexity to build be O(NlogN)?

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

      for more info, here's the link.

      → Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it +6 Vote: I do not like it

You can solve this problem offline using range trees as there are no update operations.

Compress all the values and than iterate through them (note that there will be at most n + q distinct values). At each iteration i add all the numbers equal to i to your range tree(add 1 to their initial position in array) and answer to all the queries where x = i.The answer to the query will be the sum of the numbers in the range tree from position l to r.

Thus the complexity is O((q + n) * log(n)).

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

First note 2 things.

  1. There is no update operations
  2. You found a O(q * sqrt n * log n) solution

Why the log n factor? Can you eliminate it? As there is no update, you can do it in O(1). Think about it.

EDIT If the range of the domain is too high. This won't work :(

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

    If I eliminate log n factor, then in worst case, will it pass in 1 sec, for the given constraints?

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

      Depends on the OJ. In CF, yes.

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

        I am not able to find any way to eliminate log factor.

        Since, x may be changed in every query, I should binary search x on each of the SQRT(n) sorted blocks.

        How can I eliminate this log factor ?

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

You can use a persistent segment tree. Using it you can find the number of interesting integers on prefixes [0;L - 1] and [0;R]. Then you can easily compute the answer. Complexion is O(q * logn) both for time and memory.

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

    I never used persistent segment tree before. So, if you explain the idea more clearly, it would be easier to understand for me.

    Also beside anudeep's blog, is there any good resource to learn it easily?

    I would be thankful to you !!

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

      Well, the idea of the solution is to build sum ST over integer line. Once when we meet array element ai we add 1 to the corresponding vertex of segment tree. For every update, we should do a new ST version by adding log(N) new vertexes. Then, when getting the answer, we are going back to the versions L - 1 and R and getting prefix sums on segments [0;x).

      Unfortunately, I don't really know good resources where persistent ST is explained. Well, I've learned segment tree from here. Unfortunately, it's only in Russian.

      → Reply
»
8 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Since there is no need to update array I suppose that it is possible to solve this problem via preffix sum. Correct me if I am wrong.

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

    How to solve this problem via prefix sum ? Can you please elaborate?

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

      Create an array of n elements. If element in original array is less than x change value to 1. Then calculate preffix sum.

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

        x is different for each query.

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

As there is no update operation, you can solve this problem using Sorting + BIT.

int n,a[MAX],q;    //size of array and array and number of queries
data query[MAX];    //query denotes array of 3 values - l,r,x,i(position of that query in the initial order of input)
int i,cur,val;
int bit[MAX];    //binary indexed tree initially all values 0
vector<pair<int,int> > g;    //to store pair of element of array and index of that element
for(i=1;i<=n;i++)
    g.push_back(make_pair(a[i],i);
sort(g.begin(),g.end());    //sort vector as per element
curr=0;    //curr denotes that all the first (curr-1) values of g have been updated in BIT
sort(query,query+q,way);    //way sorts array according to x
for(i=0;i<q;i++)
{
    val=query[i].x;
    while(curr<n&&g[curr].first<val)
    {
        updateBIT(1,g[curr].second);    //add value 1 at index g[curr].second
        curr++;
    }
    //now bit contains 1 at those indexes whose value is less than val
    //now we only need to count the number of values in BIT between l and r
    ans[query[i].i]=queryBIT(query[i].r)-queryBIT(query[i].l-1);
}
→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shahidul_brur (previous revision, new revision, compare).

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

You can remove logn from your sqrt decomposition solution by compressing the numbers and using prefix sums instead of binary search.

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

    I don't understand how to do it. Please explain it with example?

    → Reply