传送门：P16799 [蓝桥杯 2026 国 B] 实验数据
更佳的阅读体验：洛谷 P16799 题解

没错笔者去参赛了，虽然赛时做到这种题确实有点难绷，猜你想找 P1471 方差、P5142 区间方差。这篇题解主要写给初学线段树的同学，如果你有一定基础，想必你已经做过上面两题了。

简要题意：给你一个序列，你需要支持单点修改和查询区间和、区间方差。$n \le 10^5$。

如果你做过洛谷的线段树板子，那么此时你已经会了最基础的区间和查询。

但题目还要求你求出区间方差，此时你已经推了一百页公式，发现无论如何也推不出来只用区间和求解的方案。怎么办呢？

来推一下式子吧。

$$ \begin{align} \text{Var} = & \sum_{i = l}^r \left (a_i - \overline{a} \right )^2 \\ = & \sum_{i = l}^r a_i^2 + \sum_{i = l}^r \overline{a}^2 - 2 \cdot \sum_{i = l}^r \left ( a_i \cdot \overline{a} \right ) \\ = & \sum_{i = l}^r a_i^2 + (r - l + 1) \cdot \overline{a}^2 - 2 \cdot (r - l + 1) \cdot \overline{a}^2 \\ = & \sum_{i = l}^r a_i^2 - (r - l + 1) \cdot \overline{a}^2 \\ = & \sum_{i = l}^r a_i^2 - (r - l + 1) \cdot \left ( \dfrac{\sum \limits_{i = l}^r a_i}{r - l + 1} \right )^2 \\ = & \sum_{i = 1}^r a_i^2 - \dfrac{\left ( \sum \limits_{i = l}^r a_i \right )^2}{r - l + 1} \end{align} $$

好像推不下去了，但至少已经出现了一个我们熟悉的区间求和。但还有一个求平方和，是否有办法处理这个呢？

答案是肯定的。我们考虑线段树本身的结构，似乎只要是可以支持 push up 和 push down 操作的数据，就都可以拿线段树来维护，那平方和当然也满足。

因此，我们只需要让这一棵线段树多维护一个区间平方和即可。因为本题只需要支持单点修改，所以甚至不需要 lazy tag 和 push down。

当然，你还需要注意模意义下的除法需要通过乘它的乘法逆元来实现。

时间复杂度 $O(n \log n)$。

#include <iostream>
#define ls(p) t[p].lson
#define rs(p) t[p].rson
#define mid (l + r >> 1)
using namespace std;
using ll = long long;

const int N = 3e5 + 10;
const ll MOD = 998244353;
int n, m, op, l, r, k;
ll a[N], x;
struct seg_tree {
    int rt[N << 1], tot;
    struct node {
        int lson, rson;
        ll sum, sqsum;
    } t[N << 1];

    void pushup(int p) {
        t[p].sum = (t[ls(p)].sum + t[rs(p)].sum) % MOD;
        t[p].sqsum = (t[ls(p)].sqsum + t[rs(p)].sqsum) % MOD;
    }

    void build(int &p, int l, int r) {
        p = ++tot;
        if (l == r) return t[p].sum = a[l] % MOD, t[p].sqsum = a[l] * a[l] % MOD, void();
        build(ls(p), l, mid);
        build(rs(p), mid + 1, r);
        pushup(p);
    }

    void update(int p, int l, int r, int k, ll x) {
        if (l > k || r < k) return;
        if (l == r) return t[p].sum = x % MOD, t[p].sqsum = x * x % MOD, void();
        update(ls(p), l, mid, k, x);
        update(rs(p), mid + 1, r, k, x);
        pushup(p);
    }

    ll query_sum(int p, int l, int r, int L, int R) {
        if (l > R || r < L) return 0;
        if (l >= L && r <= R) return t[p].sum;
        return (query_sum(ls(p), l, mid, L, R) + query_sum(rs(p), mid + 1, r, L, R)) % MOD;
    }

    ll query_sqsum(int p, int l, int r, int L, int R) {
        if (l > R || r < L) return 0;
        if (l >= L && r <= R) return t[p].sqsum;
        return (query_sqsum(ls(p), l, mid, L, R) + query_sqsum(rs(p), mid + 1, r, L, R)) % MOD;
    }
} tree;

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD, b >>= 1;
    } return res;
}

ll aver(int l, int r) {
    return tree.query_sum(tree.rt[1], 1, n, l, r) * qpow(r - l + 1, MOD - 2) % MOD;
}

ll var(int l, int r) {
    ll sum = tree.query_sum(tree.rt[1], 1, n, l, r);
    return ((tree.query_sqsum(tree.rt[1], 1, n, l, r) - sum * sum % MOD * qpow(r - l + 1, MOD - 2) % MOD) % MOD + MOD) % MOD;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    tree.build(tree.rt[1], 1, n);
    while (m--) {
        cin >> op;
        if (op == 1) cin >> l >> r, cout << aver(l, r) << ' ' << var(l, r) << '\n';
        else cin >> k >> x, tree.update(tree.rt[1], 1, n, k, x);
    } return 0;
}