×

# Need help In a segment tree problem

 0 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. @freeloop asked 30 May, 19:34 4★lakh 139●5 accept rate: 23% Please provide some idea for this problem. No progress till now. (30 May, 23:08) lakh4★ 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. (31 May, 02:05) @vivek_1998299 can u validate my approach? (31 May, 13:30)

 0 Can you share question link? answered 30 May, 19:46 11●2 accept rate: 0% Actually my friend asked me this problem some days ago. (30 May, 19:48) lakh4★
 0 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. answered 30 May, 20:44 1●1 accept rate: 0% array A[]= -1 1 -1 1 -1 1.......-1 1 and query [1:N] in this case complexity would be O(N) per query (30 May, 20:59) @vivek_1998299 can you suggest some optimization or some other approach?? (30 May, 21:17) lakh4★ How will it be O(N logN) in the case Vivek pointed out? (30 May, 21:58) Yeah my bad. It is N + N / 2 + N / 4 ... < 2 * N (30 May, 22:11)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×825
×685
×110
×65