P5142 区间方差

题目描述

Note

定义平均数 $a$ 为:

a = \frac{1}{n} \sum_{i = 1}^{n} a_{i}

定义它的方差 $d$ 为:

d = \frac{1}{n} \sum_{i = 1}^{n} (a_{i} - a)^{2}

现在给定一个长度为 $n$ 的序列 $b_{1}, b_{2} \dots b_{n}$ 。你需要支持两种操作。每种操作的格式为 c x y。

若 $c = 1$ ，为修改操作，代表将 $b_{x}$ 赋值为 $y$ 。

若 $c = 2$ ，为查询操作，代表查询 $b_{x}$ 到 $b_{y}$ 的方差。

为了避免浮点数误差，请以分数取模形式输出结果（对（ $10^{9} + 7$ ）取模）。

$1 \leq n, m \leq 1 \times 10^{5}$ ， $1 \leq b_{i} \leq 1 \times 10^{9}$ ， $1 \leq x \leq n$ 。对于操作 1， $1 \leq y \leq 1 \times 10^{9}$ 。对于操作 2， $x \leq y \leq n$ 。

输入格式

第一行两个整数 $n, m$ ，代表序列 $b$ 的长度为 $n$ ，有 $m$ 个操作。

第二行 $n$ 个整数 $b_{i}$ ，表示序列 $b$ 的初始值。

下面有 $m$ 行整数，每行格式为 c x y，含义如上文所示。保证所有操作合法。

输出格式

对于每个操作 2，输出一行。

Solution

数学/树状数组/线段树

可以将求该区间的方差进行化简：
$d = \frac{1}{n} \sum_{i = 1}^{n} (a_{i} - a)^{2} = \frac{1}{n} \sum (a_{i}^{2} - 2 \times a_{i} \times \overset{―}{a} + {\overset{―}{a}}^{2}) = \frac{1}{n} \sum a_{i}^{2} - \frac{2}{n} \sum a_{i} \times \overset{―}{a} + \frac{1}{n} \sum {\overset{―}{a}}^{2}$

$\leftrightarrow \frac{1}{n} (\sum a_{i}^{2} - 2 \times \overset{―}{a} \times n \times \overset{―}{a} + n \times {\overset{―}{a}}^{2}) = \frac{1}{n} \sum a_{i}^{2} - {\overset{―}{a}}^{2}$

$(n \times \overset{―}{a} = \sum a_{i})$

$d = \frac{1}{n} \sum a_{i}^{2} - {(\frac{\sum a_{i}}{n})}^{2}$

用树状数组则需要维护区间和，区间平方和两个树状数组。
(待更 $\dots$ )

#define int long long
#define lowbit(x) x&(-x)
const int mod = 1e9 + 7;
int n, m, tr1[100010], tr2[100010];
int qpow(int a) {
    int b = mod - 2, ans = 1;
    while (b) {
        if (b & 1)ans = (a * ans) % mod;
        a = (a * a) % mod;b >>= 1;
    }
    return ans;
}
void add(int tr[], int x, int k) {
    while (x <= n)tr[x] = (tr[x] + k) % mod, x += lowbit(x);
}
int query(int tr[], int x) {
    int ans = 0;
    while (x)ans = (ans + tr[x]) % mod, x -= lowbit(x);
    return ans % mod;
}
void solve() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;
        add(tr1, i, x % mod);
        add(tr2, i, (x * x) % mod);
    }
    while (m--) {
        int op, x, y;cin >> op >> x >> y;
        if (op == 1) {
            int p1 = (query(tr1, x) - query(tr1, x - 1) + mod) % mod;
            int p2 = (query(tr2, x) - query(tr2, x - 1) + mod) % mod;
            add(tr1, x, (y - p1) % mod);
            add(tr2, x, (y * y - p2 + mod) % mod);
        } else {
            int sum = (query(tr1, y) - query(tr1, x - 1) + mod) % mod;
            int sqsum = (query(tr2, y) - query(tr2, x - 1) + mod) % mod;
            int inv = qpow(y - x + 1);
            int ans1 = (sum * inv) % mod;
            int ans2 = (sqsum * inv) % mod;
            int ans = ans2 % mod - (ans1 * ans1) % mod;
            cout << (ans + mod) % mod << '\n';
        }
    }
}