Any easy way for Count numbers in a range : Segment Tree , Lazy

general
, ,
1

given A[1…N] and K two types of query :

type-1 : count number in range [L R] such that A[i] >= K.

type-2 : given no X and range [L R], add value x to all numbers in given range A[i] += X .

1 <= N ,Q <= 10 ^ 5 [ no of elements and no of queries ]

-10^9 <= A[i] ,X <= 10^9 [X is different for each query]

-10^18 <= K <= 10^18

1 <= L <= R <= N

EX :

5 6 2 [N Q K]

1 -2 3 -4 5 [Array A]

1 2 4 [type L R ]

1 3 5

2 1 4 2 [type L R X]

1 1 5

2 1 4 -1

1 1 3

Output :

1

2

3

2

Observation : K is same for all query type -1

Expected Runtime : O(N * logQ)

I was trying such a standard problem , Any possible segment-tree,lazy solution O(N * logQ) so it will be also useful in Tree-path HLD problems O(Q * log N * log N)

Thanks in Advance.

1 Like
2

Nice problem :slight_smile:
this problem can be easily solved using square root decomposition method.

We can divide the initial n numbers into B buckets, sort the number in each buckets and maintain the total add val in each bucket. Then for each query:

“Add” update interval [a, b] with c

we only need to rebuild at most two buckets and add c to (b - a) / BUCKET_SIZE buckets

“Query” query interval [a, b] >= c

we only need to scan at most two buckets with each value one by one and quick go through (b-a) / BUCKET_SIZE buckets with binary search quickly

It should be run in O( N/BUCKET_SIZE * log(BUCKET_SIZE, 2)) for each query, which is smaller than bruteforce method( O(N)). Though it’s bigger than O(logN), it may be sufficient in most cases.

5 Likes
3

@yash_chauhan28, please you explain your approach using code.

4

it depends on the problem like is where to be use -:

  1. if you want to find number of elements for more than one ranges than i’ll suggest that use any sorting technique.

exp : suppose you want find no of elements for ranges :- [a,b] [d,b] [c,d] etc

  1. if you want yo find only for one range than :-

    for(i=;i<n;i++)

{ if(array[i] >= a && array[i] <= b)

count++;
}

Hope i am right!

5

As i mentioned it will be also useful in Tree-path HLD problems O(Q * log N * log N) if each above query can be answered in O(log n)

6

Sorry,I can solve this problem(only with sqrt(n)log(n) or log^2(n)),if you need this solution,please write me!

7

It’s(sqrt(n)*log(n))(yash_chauhan28’s solution)! The log^2(n) solution is let make a segment tree with sorted subarray from l to r! Then let’s do a bin.search(the amount of elements>=k+x)!
It will be work: nlog(n)- memory, qlogn+nlogn time

8

I am just explaining @yash_chauhan28 answer here.

Let the array be A =[1, 4, 3, 5, 2, 7, 4, 9, 8]. Divide it into segments of size BUCKET_SIZE (say ROOT(N)).

then, it will look like A = [1, 4, 3] [5, 2, 7] [4, 9, 8]. Then sort each segment separately and stor these somewhere else, DO NOT modify the array A.
for this purpose lets say we created a list of vectors B = [1, 3, 4] [2, 5, 7] [4, 9, 8]

For update query, say, add 4 from 2 to 8 (1-based indexing). Do naive updation on array A for range which partially overlap with buckets, these are the elements which lies at the extremes of the update range, and then again sort these effected buckets and update vector list B. There can be at most two effected buckets.

For segments which lies completely inside update range, just add value 4 to their lazy term.

In our example, after updation array A would be = [1, 7, 8] [2, 5, 7] [8, 13, 8]

                        4  --- lazy term of segment 2

and B = [1, 7, 8] [2, 5, 7] [8, 8, 13]

We just needed to sort two segments of size ROOT(N), time = O(ROOT(N) * log N)

also we needed to add value 4 to the middle segments which can be at most ROOT(N)

Total update time = O(ROOT(N) + ROOT(N) * LogN) = *O(ROOT(N)LogN)

Query is straight forward. Naively count the elements of array A from the extreme which partially overlaps with query range.
For middle O(ROOT(N)) segments do a binary search for k + lazy(segment), in vector list B. Time = O(ROOT(N) * LogN)

Thus each query is answered in O(ROOT(N) * LogN)

For O(Log^2(N)) solution which @glebodin proposed, you can read rachitjain’s answer on this link.

There is also a Log(N) per each query solution explained at the last in that link.

9

@joney_000, can u provide link to this problem, so that I can try.