A range query problem

Given an array of integers of length N and an integer K. We have to answer N queries. Each query consist of some range [L, R]. In each query We have to decrease the value of the array elements in this range by 1 and answer how many integers in the range [j, N] is less than or equal to K (where j is the query number we are currently answering).

Note that the values that we subtract in ith query will be reflected in all the further queries also.

Constraints: K <= N<= 10^5

This question is asked during interview and it can be solved within N(logN)^2 complexity.
@l_returns @anon55659401 @aryanc403 please help!

4 Likes

i googled and found this cf blog https://codeforces.com/blog/entry/15729 . i think these problems are called as partial sum. any link of that problem which you were describing ??

I don’t think it’s a partial sum problem. Could you please explain your idea a little bit?

And as it is an interview question, I don’t have any links :frowning_face:

1 Like

no bro idk . i just said i think so after reading that blog .

NP. Please share this question to the one whom you think can help (or may be in cf) :slight_smile:

1 Like

i think you could better create a cf blog that might help.

Use Lazy Propagation with Persistent Segment Tree.
Persistent segment will help you answer numbers <=K and and Lazy Propagation will help you with range updates.

Read this to be familiar with their combo:- https://www.quora.com/How-can-we-apply-lazy-propagation-to-persistent-segment-trees

2 Likes

@l_returns I know you know persistence(segment-tree) very well. Can you mention a good place to study and practice it ? Will be very grateful to you :slight_smile:

1 Like

You know it as well :slight_smile:

1 Like

No:sleepy::sleepy::sleepy::sleepy::sleepy::sleepy::sleepy::sleepy:

Idk any particular good resource. Saw persistent Segtree on geeksforgeeks.
Which allows to code different types of persistent trees like persistent trie as well

1 Like

I don’t understand completely. Can you explain a little bit more?

1 Like

CP Algorithms is also a good resource to learn Persistent Segment Trees and many other algorithms in general. It’s the English translation of the Russian website EMAXX
Persistent Segment Trees

I know persistent segment trees. Just want to know how we use it here

I’ll answer it in sometime…right now busy with life.

I have a solution which will time out because its complexity is O(n √n log(√n)).
So as you would guess by the √n factor its obviously sqrt decomposition.
Divide the array into √n blocks and sort each block. Now for a given opearation don’t update the block(which is fully overlapping with the concerned range [L, R]) but instead maintain a counter array of size √n which maintains the information how many times the block was updated completely(i.e no times all the array elements of the block where reduced by 1). Update the partially intersecting blocks manually(Don’t forget to sort the 2 block which intersects partially with [L, R])

Now after update you consider range from [j, N] and check how many elements in each block is less than k which can be done with binary search(dont forget to count the no of times the block was updated completely).
I will think of some O(n log(n)^2) solution , because you can see clearly that my solution is not taking the advantage of the fact that upper bound for query is always N.
I will just update this post if I come up with some solution.

I liked the problem, may I know which company interview problem is this ?

4 Likes

Thanks for your help! If you come up with O(logN^2) then please upload it.

I think your approach can easily be converted to O(N*sqrt(N)) by maintaining an array of size K at each bucket and maintaining prefix-sum in that !

If you don’t mind then can I know how you land upon this solution?
I know sqrt decomposition but I never thought of using it here. It will be helpful if you can share your experience when to think about which approach.

It’s from codenation (or amazon). Actually this problem I get from my fellow mate who just get offer from Amazon (previously he was interviewed at codenation also).

1 Like

May Challenge had SONGIF , which required similar type of updates though the query required implementation of CHT .

Please elaborate a little about the prefix sum you would maintain in each block to eliminate the log factor of complexity

find the minimum in a bucket and subtract every element from it and then all the elements will be in the range of sqrt(N) and then just maintain the count of each elements in reverse way (arr[i] = how many elements occurs exactly i times) and calculate the prefix sum to answer “how many elements occurs less than K times”

How will you maintain this info even when the partial updates of the buckets is done?