【解题报告】P1471 方差 解题报告

$\texttt{Description}$

给定一个数列，要求维护区间平均数、区间方差，支持区间加法。

$\texttt{Solution}$

显然，查询区间平均数，只需要求出区间和，再除以区间长度即可，这是最基础的板子。

那么解决区间方差的问题。

众所周知，方差的公式为：

$$s^2 = \dfrac{1}{n} \times [(a_1 - \overline{a}) ^ 2 + (a_2 - \overline{a}) ^ 2 + \cdots + (a_n - \overline{a}) ^ 2] $$

根据 $(a + b) ^ 2 = a^2 + b^2 + 2ab$，可以对上式进行展开：

$$s^2 = \dfrac{1}{n} \times [(a_1^2 + \overline{a} ^ 2 - 2a_1\overline{a}) + (a_2^2 + \overline{a} ^ 2 - 2a_2\overline{a}) + \cdots + (a_n^2 + \overline{a} ^ 2 - 2a_n\overline{a})] $$

对该式进行合并：

$$s^2 = \dfrac{1}{n} \times [(a_1^2 + a_2^2 + \cdots + a_n^2) + n \times \overline{a} ^ 2 - 2 \times (a _ 1 + a_2 + \cdots + a_n) \times \overline{a}] $$

根据 $\overline{a} \times n = a_1 + a_2 + \cdots + a_n$，可以进行化简：

$$s^2 = \dfrac{1}{n} \times[(a_1^2 + a_2^2 + \cdots + a_n^2) - n \times \overline{a} ^ 2] $$

那么，问题的突破口来到了如何维护区间平方和。

建树的部分很简单，把叶子结点赋值为数列里对应数字的平方，把非叶子结点赋值为左右叶子结点之和即可。

考虑区间加法的同时维护区间平方和。

若我们要把 $k_l^2 + k_{l + 1}^2 + \cdots + k_{r} ^ 2$ 变为 $(k_l + v)^2 + (k_{l + 1} + v)^2 + \cdots + (k_r + v) ^ 2$，则可以把后式进行展开成：

$$(k_l^2 + v^2 + 2\times v \times k_l) + (k_{l + 1} ^ 2 + v^2 + 2 \times v \times k_{l + 1}) + \cdots + (k_r ^2 + v^2 + 2 \times v \times k_r) $$

进行合并，得：

$$(k_l^2 + k_{l + 1} ^2 + \cdots + k_r^2) + (n\times v^2) + 2\times v\times (k_l + k_l+1 + \cdots + k_r) $$

这样就可以正常维护、下传标记了。

但是要注意，更新的时候要先更新区间平方和，再更新区间和。因为最后一个式子的第一项 $(k_l^2 + k_{l + 1} ^2 + \cdots + k_r^2)$ 中，$k$ 指的是还没更新的时候的数列。

最后放一下代码，这题的细节还是不少的。

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define maxn 100005
struct SegmentTree {
    int l, r;
    double add;
    double sum, squ;
} t[maxn * 4];
int n, m;
double a[maxn];

void push_up(int p) {
    t[p].sum = t[p << 1].sum + t[(p << 1) | 1].sum;
    t[p].squ = t[p << 1].squ + t[(p << 1) | 1].squ;
}

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) { t[p].sum = a[l], t[p].squ = a[l] * a[l]; return; }
    int mid = (t[p].l + t[p].r) >> 1;
    build(p << 1, l, mid), build((p << 1) | 1, mid + 1, r);
    push_up(p);
}

void spread(int p) {
    if (t[p].add) {
        t[p << 1].squ += 2 * t[p].add * t[p << 1].sum + t[p].add * t[p].add * (t[p << 1].r - t[p << 1].l + 1);
        t[(p << 1) | 1].squ += 2 * t[p].add * t[(p << 1) | 1].sum + t[p].add * t[p].add * (t[(p << 1) | 1].r - t[(p << 1) | 1].l + 1);
        t[p << 1].sum += (t[p << 1].r - t[p << 1].l + 1) * t[p].add;
        t[(p << 1) | 1].sum += (t[(p << 1) | 1].r - t[(p << 1) | 1].l + 1) * t[p].add;
        t[p << 1].add += t[p].add, t[(p << 1) | 1].add += t[p].add;
        t[p].add = 0;
    }
}

void update(int p, int l, int r, double v) {
    if (l <= t[p].l && r >= t[p].r) {
        t[p].squ += 2 * v * t[p].sum + v * v * (t[p].r - t[p].l + 1);
        t[p].sum += (t[p].r - t[p].l + 1) * v;
        t[p].add += v;
        return;
    }
    spread(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) update(p << 1, l, r, v);
    if (r > mid) update((p << 1) | 1, l, r, v);
    push_up(p);
}

double ask(int p, int l, int r) {
    if (l <= t[p].l && r >= t[p].r) return t[p].sum;
    spread(p);
    int mid = (t[p].l + t[p].r) >> 1; double val = 0;
    if (l <= mid) val += ask(p << 1, l, r);
    if (r > mid) val += ask((p << 1) | 1, l, r);
    return val;
}

double query(int p, int l, int r) {
    if (l <= t[p].l && r >= t[p].r) return t[p].squ;
    spread(p);
    int mid = (t[p].l + t[p].r) >> 1; double val = 0;
    if (l <= mid) val += query(p << 1, l, r);
    if (r > mid) val += query((p << 1) | 1, l, r);
    return val;
}

double avg(int x, int y) {
    return ask(1, x, y) / (1.0 * (y - x + 1));
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (m--) {
        int op, x, y; double k;
        cin >> op >> x >> y;
        if (x > y) swap(x, y);
        if (op == 1) {
            cin >> k;
            update(1, x, y, k);
        }
        else if (op == 2) printf("%0.4lf\n", avg(x, y));
        else printf("%0.4f\n", (query(1, x, y) / (1.0 * (y - x + 1)) - avg(x, y) * avg(x, y)));
    }
    return 0;
}