game_changer007's blog

range marked query
By game_changer007, 10 years ago, In English

Hi,There are certain queries like [l,r] where every element is maked between array indexes l to r; and all queries i want to know the total number of marked numbers.

Is there any faster way to do it besides iterating for each query from l to r and finally counting number of marked values?

eg- query=3 1 2 4 5 2 4

final array = 1 1 1 1 1 0 0.... ans=5

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

»
10 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

Yes there are plenty of cool methods for this problem.

If you are asked how many are the marked values after all marking queries, then there is a cool O(N+Q) algorithm. Here it is:

Create an array counter[] initially being zeroed. Every time you get a query to mark [l;r] increase counter[l] and decrease counter[r+1].

counter[l]++;
counter[r+1]--;

Now after all queries, go through the array from left to right keeping a variable sum that is initially zero. At the i-th step add counter[i] to the sum. It can easily be seen that at the i-th step sum will be holding the amount of queries that covered the corresponding element, so if it is 0 then the element isn't marked, and if it isn't 0 -> it is marked.

for (i=1;i<=n;i++)
{
    sum=sum+counter[i];
    
    if (sum>0)
    ans++;
}

Here is how it works on the example you provided:

Query 1 2 
counter[1]++, counter[3]--
Query 4 5
counter[4]++, counter[6]--
Query 2 4
counter[2]++, counter[5]--

The counter array looks as
1 1 -1 1 -1 -1 0 0....

So the sum value will take values
1 2 1 2 1 0 0 0 ...

Clearly the values where sum isn't 0 are 5, hence the answer! :)

The algorithm works and has O(N+Q) complexity.

If you have queries for the count and queries for marking simultaniously and you have to answer them online, then you can use a quite harder approach called lazy propagation on segment trees. However for the problem you described, the above solution should work!

Good luck, and feel free to ask if you have any questions :)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    counter[l]++;
counter[r+1]--;

    Could you please prove why this works ? I've seen this somewhere before, but unable to understand it.

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

      Well increasing counter[l] and decreasing counter[r+1] means that later as you sum them up, at point l the sum will increase by one, and then at point r+1 it will decrease by one, in a way neutralizing the increase. So doing those two operations guarantees that the sum will be increased by one in the interval [l;r] when you process later. It is easy to see that therefore the sum will at any point always give the number of intervals that covered the current element.

      Hope you understood! :)

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

    Thanx,but how to do it if array is an infinite array

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

      Oh, if your array is "infinite" then you can process the queries offline in O(QlogQ) to get your answer. Here is how it goes:

      Firstly, sort the queries in increasing order of the beginning. So the queries you gave as an example would be sorted as {1,2} < {2,4} < {4,5}. Now you start processing them from left to right and in a way "merging them". So if the start of the i+1-th query is equal or less to the end of the i-th query, then obviously you can marge them into one query. That is:

      {L[i]; R[i]} < {L[i+1]; R[i+1]}

if (L[i+1]<=R[i])
Merge them into {L[i];R[i+1]}

      If you can't merge them, then simply the current interval will be secluded from the rest, so you can add its length to the answer and continue on merging. In the program itself actually merging is unnecessary, it's more for imagining how it works. Here is the code I would use once the queries are sorted in the mentioned way:

      beg=L[1];
end=R[1]; //initialization of the "current" interval
for (i=2;i<=q;i++)
{
    if (L[i]<=end)
    end=R[i]; //merging the query to the current interval as it overlaps
    else
    {
        ans=ans+(end-beg+1) //the query doesn't overlap,
        beg=L[i]; //therefore we forget the interval and continue with a new one
        end=R[i];
    }
}
ans=ans+(end-beg+1);

      The above code should produce correct answers. In a way it merges the overlapping queries, so you are left with only non-intersecting queries, which can easily then be processed by simply summing their lengths. It is easy to see that if two queries overlap, the above algorithm will process them and merge them into one, therefore the result will be correct.

      Hope I helped, feel free to ask if you didn't understand something :)

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

[L,r] = [2,4]

→ Reply