线段树:维护方差
由 P1471 方差 引发。
其实就是线段树 + 一点数学。
推理 1
方差基本公式( 太难打了,就用 了):
其中 ,也就是平均数。下面就省略求和的上下界咯。
而
也就是说
也就是说我们只需要维护 和 就可以维护方差了,也就是维护区间和、区间平方和。
推理 2
如何用 LazyTag 维护平方和?考虑对区间内所有的数 ,
注意,在下放 LazyTag 的时候,应该先计算新的 ,因为上面这个式子是通过旧的 计算得的。
实现
这里只展示关键代码。节点设计:
struct Node {
int sum, sum2, tag;
};
void pushdown(int l, int r, int m, int cur) {
if (nodes[cur].tag == 0 or l == r) return;
int lsN = m - l + 1, rsN = r - m; // 左右儿子的区间大小
Float x = nodes[cur].tag;
// 先更新平方和
nodes[cur << 1].sum2 += 2 * x * nodes[cur << 1].sum + lsN * x * x;
nodes[cur << 1 | 1].sum2 += 2 * x * nodes[cur << 1 | 1].sum + rsN * x * x;
// 再更新区间和
nodes[cur << 1].sum += x * lsN;
nodes[cur << 1 | 1].sum += x * rsN;
// 下放 tag
nodes[cur << 1].tag += x;
nodes[cur << 1 | 1].tag += x;
nodes[cur].tag = 0;
}
实际写的时候我习惯把 pushup()
也封装一下,因为代码有点长。我们只写线段树的 getsum()
和 getsum2()
方法,具体求方差什么的留给 main()
里面的逻辑做。