UVA 12501: Bulky process of Reduction
Link: http://uva.onlinejudge.org/contests/3104bd11ede/12501.html
Topic: Segment Tree with Lazy Propagation
This problem was given on BGC Trust University Programming Contest 12. But during the contest my team could not solve it. Later I tried this problem, got an analysis from Progkriya.com. But did not understand it properly, mayb I am newbie. 😦 Got TLE with that approach [ maybe implementation problem].
But after some googling, I have found this way. And this approach is easy to catch and a new trick to attack segment tree.
Problem Description Summary:
You will be given an array of N size, initialized with 100.
Then two of types of operation will be given.
1. change i j u
for this operation, you need to increase the numbers between index I and j by u.
for an example:
change 1 3 3
Index  1  2  3 
Before Operation  100  100  100 
After Operation  103  103  103 
2. query i j
for this operation , you need to give some output according to the interval
for an example:
query 1 3
Index  1  2  3 
Before Operation  100  106  104 
Output will be
1*a[i]+ 2*a[i+1]+… +n*a[j]
So for this query output will be
1*100+2*106+3*104= 100+212+312=624
You need to print 624.
How to solve this problem??
After reading the problem, you might think, update can be done, but how to do the query. Crap!!
As we might think that, we need to traverse all the node between I and j. that would take O(nlogn). For n query, worst case will be O(n^{2}logn).
That will give you TLE for sure.
Then how to solve it, any Mathematical formulation? So far I haven’t found any direct mathematical formula for this. But there is a Mathematical equation approach. Let’s find it out…
What if we initialize the array with this way.
Index  1  2  3  4  5 
Primary Sum  100  100  100  100  100 
Secondary Sum  100  200  300  400  500 
Formula  Index*100= 1*100  2*100  3*100  4*100  5*100 
Remember this pattern of secondary sum, we need that later.
Hmm, now if a query comes for this interval [3, 5], output can be found with this formula
Secondary Sum of [3,5] – Primary sum of [3,5] * (31)
Generalized Equation:
For interval [ i , j ],
Output will be: Secondary sum of [ i , j] – Primary sum of [ i, j] * (i1)
Solve this equation for arbitrary interval; check that you really get the correct output.
Now update process is kinda complex. For update process, you need to update both primary sum and secondary sum. Updating primary sum is trivial, but secondary sum is some Mathematical.
For secondary sum, we need to preserve the pattern property as we gave during the initialization.
If the operation comes like this way:
change 3 5 3
Index  1  2  3  4  5 
Primary Sum Before Change  100  100  100  100  100 
Secondary Sum before Change  100  200  300  400  500 
Primary Sum After Change  100  100  103  103  103 
Secondary Sum after Change  100  100  Secondary Sum before Change+ index*u=300+ 3*3=309

400+4*3=412  500+5*3=515 
So now its upon you that how do you handle the lazy propagation.
Again If you need the code, please let me know. 🙂