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!
i googled and found this cf blog Algorithm Gym :: Data structures - Codeforces . i think these problems are called as partial sum. any link of that problem which you were describing ??
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.
Idk any particular good resource. Saw persistent Segtree on geeksforgeeks.
Which allows to code different types of persistent trees like persistent trie as well
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 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 ?
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).
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”
