P1471 方差 分析
__ryp__
·
·
个人记录
题目要求的是一个区间内的平均数和方差。很明显是线段树的题目。
容易得到：
\begin{aligned}
s^2 & = \frac 1 n \sum\limits_{i=1}^n (x_i - \bar x)^2 \\
& = (x_1 - \bar x)^2 + (x_2 - \bar x)^2 + \cdots + (x_n - \bar x)^2 \\
& = x_1^2 + x_2^2 + \cdots x_n^2 + n\bar x^2 - 2\bar x(x_1 + x_2 + \cdots + x_n) \\
& = \sum\limits_{i=1}^n x_i^2 -2\bar x \sum\limits_{i=1}^n x_i + n\bar x^2 \\
& = \frac 1 n\sum\limits_{i=1}^n x_i^2 -\frac 1 {n^2} (\sum\limits_{i=1}^n x_i)^2
\end{aligned}
于是对一个区间，我们只需要维护它的总和以及平方和即可。