跳到主要内容

线段树:维护方差

P1471 方差 引发。

其实就是线段树 + 一点数学。

推理 1

方差基本公式(σ2\sigma^2 太难打了,就用 s2s^2 了):

s2=1ni=1n(aiaˉ)2.s^2 = \frac{1}{n}\sum_{i=1}^n{(a_i-\bar{a})^2}.

其中 aˉ=1nai\bar{a}=\frac{1}{n}\sum a_i,也就是平均数。下面就省略求和的上下界咯。

1n(aiaˉ)2=1nai22naˉai+aˉ2.\frac{1}{n}\sum{(a_i-\bar{a})^2}=\frac{1}{n}\sum{a_i^2}-\frac{2}{n}\bar{a}\sum{a_i}+\bar{a}^2.

1naˉ=1n2ai.\frac{1}{n}\bar{a}=\frac{1}{n^2}\sum{a_i}.

也就是说

s2=1nai22n2(ai)2+1n2(ai)2=1nai21n2(ai)2s^2=\frac{1}{n}\sum{a_i^2}-\frac{2}{n^2}(\sum{a_i})^2+\frac{1}{n^2}(\sum{a_i})^2=\frac{1}{n}\sum{a_i^2}-\frac{1}{n^2}(\sum{a_i})^2

也就是说我们只需要维护 ai\sum a_iai2\sum a_i^2 就可以维护方差了,也就是维护区间和、区间平方和。

推理 2

如何用 LazyTag 维护平方和?考虑对区间内所有的数 +x+x

(ai+x)2=ai2+2xai+nx2.\sum{(a_i+x)^2} = \sum{a_i^2}+2x\sum{a_i}+nx^2.

注意,在下放 LazyTag 的时候,应该先计算新的 ai2\sum{a_i^2},因为上面这个式子是通过旧的 ai\sum a_i 计算得的。

实现

这里只展示关键代码。节点设计:

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() 里面的逻辑做。