跳到主要内容

线段树：维护方差

由 P1471 方差 引发。

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

推理 1​

方差基本公式：

σ2=1n∑i=1n(ai−aˉ)2.\sigma^2 = \frac{1}{n}\sum_{i=1}^n{(a_i-\bar{a})^2}.

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

1n∑(ai−aˉ)2=1n∑ai2−2naˉ∑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ˉ=1n2∑ai.\frac{1}{n}\bar{a}=\frac{1}{n^2}\sum{a_i}.

也就是说

σ2=1n∑ai2−2n2(∑ai)2+1n2(∑ai)2=1n∑ai2−1n2(∑ai)2\sigma^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_i 和 ∑ai2\sum a_i^2 就可以维护方差了，也就是维护区间和、区间平方和。

推理 2​

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

∑(ai+x)2=∑ai2+2x∑ai+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() 里面的逻辑做。