Hi, i was wondering how would we carry out these operation on an array using segment tree.
Formal statement of the problem.
Given an array if N positive integers, and Q queries perform these operations.
1 L R X. Decrease every element in the range [L...R] by by value X
2 L R. Return how many element in the range[L...R] are strictly greater than 0
N, Q <= 10^5
0 <= X <= 10000
Initial values of array can be as large as 1 000 000 000 What information would i have to store in each node ?
Learn about Lazy propagation.
Yes ,i have solved some problems using lazy propagation. Still not able to see how this can be done. Can you share your approach ?
I remember this problem was in contest in Codechef, here you can find editorial: https://discuss.codechef.com/questions/23736/mlchef-editorial
Consider these hints:
1. Segment Tree with each node as a sorted vector of elements in its range.
2. Lazy Propagation on the value to be subtracted.
3. Binary Search on vector for the number of elements > K.
Won't your solution require updates to vectors ? And updating vectors takes O(size of range) time. In the worst case , every update could be O(N).
Consider a simple case, where the aray is A[1...8].
First update A[5...8].
Now, query A[1...8].
You cannot maintain Lazy array for simple range sum as updates passed on A[5...8] should not affect A[1...4]. Any other way would require updating vector's , isin't it ?
No I am not updating the vectors. For each node, its lazy value will determine the amount, say K that we have to subtract form each number in this node's range. Then querying how many nos are greater than 0 in this range is same as number of elements in the NON-UPDATED vector that are greater than K.
But how shall u maintain the K that we talk about ?
Consider a simple case, where the array is A[1...8].
First update A[5...8].
Now, query A[1...8].
The lazy for A[1...8] is 0 and u will query its vector for elements greater than 0. However, we have updated elements (5, 6, 7, 8), that initially may have value > 0 , but do not now
For this, we can have two arrays, one is lazy[] and second is changed[]. lazy[node] tells the value that need to be subtracted from elements of that node, while changed[node] is the amount that have been subtracted from each element in that node till now. So we clear the lazy[node] value when we add it to the children's lazy[left/right] and also add it to changed[node]. So while querying a node, we need to see how many numbers are greater than changed[node].
I think it is good to split the problem up into three separate standard ones.
The first is to have a tree which can handle range updates, and range query for min value. i.e. Each node must store the min of its range. This requires standard lazy propagation — I'm assuming you know this.
The second is to 'walk' the tree to find the first element which is less than zero, if it exists. How do we do this? We look at the min value. If it is negative, there is a negative element in this range! Else, there isn't. So we can walk to the leaf and erase it if it is negative. Notice that we can do this repeatedly until the overall min is positive. Why? Because the complexity amortizes to O(N log N) as each leaf is only removed once.
Finally, obviously, we must keep track of which nodes are not yet erased by the above. We can use a standard sum tree.
Of course, you may combine everything here. But the reason I explain it separately is to avoid confusion about what is necessary.
Hope this helps.
It does