This is in reference to the question Rice hub in IOI 2011. I'll try to state specifically what i need so you don't have to go through the whole pdf.
when an array of points (sorted in non decreasing order), a starting index s and end index t of the segment is given calculate the absolute difference between each point in the segment s t and the mid point ( (s+t)/2 ).
i.e array: 1, 3, 5, 8, 11, 15
s: 1
t: 5
Here we have to consider the segment 3, 5, 8, 11, 15
Answer = |8-3| + |8-5| + |8-8| + |8-11| + |8-15| = 5 + 3 + 0 + 3 + 7 = 18
I want to do this in constant time. The solution suggests a way using prefix sum but i can't understand it.
Answer = (p - s)*arr[p] - (T[p] - T[s]) + (T[t + 1] - T[p +1]) - (t - p)*arr[p]
where s = starting index, t = ending index, p = (s + t)/2, T is the prefix sum array
Can you please describe the above equation so that i can understand it.
I wrote the above equation because i can't exactly copy paste as it's with Latex. Check this in case it's not clear
From all indices in the range s -> (p — 1) the equation (arr[p] — arr[ind]) will be positive, so you can represent that as # of elements in that range * arr[p] — sum of all elements from s -> p — 1. The same logic is applied from indices (p + 1) -> s except the difference will be negative, so you do sum of the elements in that range — # elements in that range * arr[p]
Thank you.
Now i understand. It's like i wrote (arr[p]-arr[i]) for every element and then simplified it. Got the common term arr[p] outside and got sum s of arr[i] by the prefix sum. :)