May 30, 2018, 7:34pm
Given an array of N(N<=10^5) elements and -10^9<=A[i]<=10^9. Q(Q<=10^5) queries are there of two types:
L R K: Add K to all numbers in range [L,R] in array.
L R: Find no. of positive elements>0 in range [L,R].
I Thought of segment tree with lazy propagation but not able to understand what info to be stored in each node. Please suggest some approach for this problem.
Can you share question link?
May 30, 2018, 7:48pm
Actually my friend asked me this problem some days ago.
I think you will need a range min query and range max query based 2 segment trees and using that you can answer the queries.
e.g. if max element in a range is less than 0 you return 0,
if min element in a range is greater than 0 you return r - l + 1.
else you go to the next level and see if one of the above condition holds.
Use lazy propagation to update the maximum and minimum values of the 2 trees. That shouldn’t be too hard.
array A= -1 1 -1 1 -1 1…-1 1
and query [1:N]
in this case complexity would be O(N) per query
May 30, 2018, 9:17pm
@vivek_1998299 can you suggest some optimization or some other approach??
I am not at all sure about this. Any counter case/feedback is appreciated!
I think you can solve this problem by maintaining a Venice Set in each node. I learned this thing just few days back and so may be I am completely wrong! From here on, I assume you have atleast had a look on the blog I mentioned.
Query of type 1 : We can use Technique as mentioned in blog with lazy propagation.
Query of type 2 : We basically need to find numbers > water_level in Set of range [L,R]. As the values are stored in multiset, we can binary search on value of water_level to find the answer.
How will it be O(N logN) in the case Vivek pointed out?
Yeah my bad. It is N + N / 2 + N / 4 … < 2 * N
May 30, 2018, 11:08pm
Please provide some idea for this problem. No progress till now.
U can do this using parallel binary search.
(Just see after which update query of first type ,a particular element becomes positive)
If u have any doubts,u can ask,i’ll elaborate it.
@vivek_1998299 can u validate my approach?
can u explain it in a more detail?
i mean how would u handle the range part?
Ohh nvm, I just figured that this approach won’t work due to mismatch of
water_level between children of a node. Thanks though
Thanx for telling about this new data structure:)
Glad my wrong approach/answer was helpful to someone xD