Variance Query

分散の定義は

$$\frac{1}{N} \sum_{i=1}^{N} {\left(A_i - \bar{A}\right)}^2$$

でしたが、下の式でも求まることが知られています。

$${\frac{1}{N} \sum_{i=1}^{N} {A_i}^2} - {\left(\bar{A}\right)}^2$$

これにより、$O(N)$ で前計算しておけば、各クエリが $O(1)$ で求まります。

このとき、計算途中で 64bit 整数におさまらない数がでてくるので、double を使おうとすると、誤差が大きくなり正しく求まりません。

大きな数からほとんど同じ大きな数を引くと有効桁数が減る、桁落ちという現象が知られています。

このような現象が起きるのは $A_i$ が大きく、分散が小さいときであるので、あらかじめ $A_i$ から平均に近い値を引いておき、$x$ からもその値を引くことで、精度よく答えが求まります。