思路

• 关键等式：方差可用 $Var = E[X^2] - (E[X])^2$ 计算。只需区间的 $sum$ 与 $sum$ 的平方和 $\sum a_i^2$。

• 数据结构：维护两个树状数组（或线段树）：

  • 一个维护区间和 $S=\sum a_i$。
  • 一个维护平方和 $Q=\sum a_i^2$。

• 操作复杂度：单点修改 $O(log n)$，区间查询 $O(log n)$。

• 计算：查询 $[l,r]$ 时，$m=r-l+1$，$Var = \dfrac{Q}{m} - \left(\dfrac{S}{m}\right)^2$。使用 $64$ 位整型累计，最终用浮点输出。

题目内容

给定 $n$ 名员工的工资序列 $a_1,a_2,...,a_n$ 。

方差 用来度量数据的离散程度，具体见下方名词解释。

现有 $q$ 次操作。每次操作有两种类型：

1.将第 $i$ 名员工的工资修改为 $x$ ;