Given a line function $y = ax + b$, it is easy to calculate the sum-of-squares distance between the line and a window of samples $(1, y_1), (2, y_2), ..., (n, y_n)$ (where $y_1$ is the oldest sample and $y_n$ is the newest):

$\sum_{x=1}^{n}(y_x - (ax + b))^2 $

I need a fast algorithm for calculating this value for a rolling window (of length `n`

) - I cannot rescan all the samples in the window every time a new sample arrives.

Obviously, some state should be saved and updated for every new sample that enters the window and every old sample leaves the window.

Notice that when a sample leaves the window, the indecies of the rest of the samples change as well - every $y_x$ becomes $y_{x-1}$. Therefore when a sample leaves the window, every other sample in the window contribute a different value to the new sum: $(y_x - (a(x-1) + b))^2$ instead of $(y_x - (ax + b))^2$.

Is there a known algorithm for calculating this? If not, can you think of one? (It is ok to have some mistakes due first-order linear approximations).

Thanks