# In the below quote from the editorial, I am able to follow it before the point where it says "This can be written in the following form" (third last statement). I can't figure out how it is able to write it in that form...
D is unfairness sum for the concerned sub list.
First, we sort the list in increasing order: X1, X2, X3,....XK,XK+1,....,XN. The next step is to find the value of D for the first K elements i.e. from X1 to XK. suppose we have calculated D for first i elements. When we include Xi+1, the value of D increases by ( |Xi+1 - X1| + |Xi+1 - X2| +....+ |Xi+1 - Xi| ), which in turn is equal to ( i*XK - (X1 + X2 + ....+Xi) ). We just need to store the sum of the current elements and repeat the step for i = 1 to k-1.
Now that we have the solution for X1 to XK, we want to calculate the same for X2 to XK+1. This can be done in O(1) time.
New unfairness sum = old unfairness sum + ( |XK+1 - X2| + |XK+1 - X3| + .... + |XK+1 - XK| ) - ( |X1 - X2| + |X1 - X3| + .... + |X1 - XK| ). This can be written in the following form:
New unfairness sum = old unfairness sum + K.(XK - X1) - K.(X1 + X2 +....+XK) + ( X1 - XK)