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.