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



Algorithm for calculating the sum-of-squares distance of a rolling window from a given line function
We have $\sum\_x (y\_x - ax-b)^2 = \sum\_x y\_x^2 - 2a \sum\_x x y\_x - 2b \sum\_x y\_x + \sum\_x (ax+b)^2$ so the only term requiring $O(n)$ time per shift is $\sum\_x x y\_x$ because an easy $O(1)$ time trick handles the other terms involving $y\_x$.


In this term, you can decrement $x$ in $O(1)$ time too because $\sum\_x (x-1) y\_x = \sum\_x x y\_x - \sum\_x y\_x$, heck you must store $\sum\_x y\_x$ anyways. After that, you could simply employ the same obvious $O(1)$ time slide trick you used for $\sum\_x y\_x^2$ and $\sum\_x y\_x$.


In fact, you need not do anything too special if terms slide off when $x=0$, i.e. you initially added $k y\_x$ and subtracted off one $y\_x$ per round.


