http://www.codechef.com/CODX2014/problems/REN2013J
can somebody explain how to apply lazy propagation for this problem
There’s no need for serious segment trees here. Notice that if an update is applied on the i-th element 10 times, it will be 0 forever. We can keep a list of non-zero elements (an STL set<>, for example), process the updates element-by-element on the corresponding range of non-zero elements, and always delete the elements that become zero; this takes O(10*N+(N+Q)logN), as each element is deleted at most once, updated at most 10 times and each query requires finding the range of elements in the set that we update. The problem now simplifies to point updates and range sum queries, which can be solved by a textbook Fenwick tree.
2 Likes
Make a segment tree such that each node contains 2 values, sum , as in the sum of elements in entire range and , max as in the maximum element in the array. Now for the update query, it can be made only log(max element in range) times before the entire range becomes zero. So perform a sort of brute force update query moving down the tree until you hit a node which is either a leaf or has max==0 and stop. In this way you will visit each node of the tree about log(max element in array) times for updates and query for sum will be just like an ordinary query for a range sum. This should pass in the given time limit.
http://www.codechef.com/viewsolution/3291936
can somebody explain the approach used here as it could be helpful to learn lazy propagation
Set. Fenwick tree. Simpler and faster to code.
How to approach this using binary indexed tree?