Need help In a segment tree problem

general
, , ,
1

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:

  1. L R K: Add K to all numbers in range [L,R] in array.
  2. 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. @freeloop

2

Can you share question link?

3

Actually my friend asked me this problem some days ago.

4

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.

5

array A[]= -1 1 -1 1 -1 1…-1 1

and query [1:N]

in this case complexity would be O(N) per query

6

@vivek_1998299 can you suggest some optimization or some other approach??

7

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.
My thought:
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.

1 Like
8

How will it be O(N logN) in the case Vivek pointed out?

9

Yeah my bad. It is N + N / 2 + N / 4 … < 2 * N

10

Please provide some idea for this problem. No progress till now.

11

U can do this using parallel binary search.

Read this:

http://codeforces.com/blog/entry/45578?mobile=false

(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.

12

@vivek_1998299 can u validate my approach?

13

can u explain it in a more detail?

i mean how would u handle the range part?

14

Ohh nvm, I just figured that this approach won’t work due to mismatch of water_level between children of a node. Thanks though :slight_smile:

15

Thanx for telling about this new data structure:)

16

Glad my wrong approach/answer was helpful to someone xD