方差

GitHub跳转原题关系图 Canvas 关系图返回列表

线段树节点同时维护区间和与平方和，用懒标记支持区间加，方差由二阶矩公式 O(log n) 求出。

OJ: luogu

题目 ID: P1471

难度:提高

标签:线段树懒标记区间加方差浮点数

日期: 2026-07-16 23:59

前置题目

luogu P3372【模板】线段树 1区间加懒标记骨架，本题多维护一个平方和字段

形式化题目

有一个长度为 $n$ 的实数数列 $a$ ，初始值给定。给出 $m$ 次操作：

对区间 $[l,r]$ 内的每个位置加上实数 $k$ ；
询问区间 $[l,r]$ 的平均数 $\overline A = \frac{1}{len}\sum a_i$ ；
询问区间 $[l,r]$ 的方差 $s^2 = \frac{1}{len}\sum(a_i - \overline A)^2$ 。

要求按顺序处理全部操作，每次询问输出一行实数，保留 4 位小数。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:10
 * update_at: 2026-08-12 22:10
 */
// brute.cpp：小数据暴力解，直接按题意逐项区间加、暴力求平均数和方差，
// 用来理解题意并辅助对拍，复杂度 O(nm)，只适合小数据。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, m;
double a[MAXN]; // a[i] 表示当前位置的当前值

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    cout << fixed << setprecision(4);

    while (m--) {
        int opt, l, r;
        cin >> opt >> l >> r;
        if (opt == 1) {
            double k;
            cin >> k;
            // 区间加：暴力逐项加。
            for (int i = l; i <= r; i++) {
                a[i] += k;
            }
        } else {
            // 查询：暴力扫描区间，同时累加和与平方和。
            double s = 0, s2 = 0;
            for (int i = l; i <= r; i++) {
                s += a[i];
                s2 += a[i] * a[i];
            }
            double len = r - l + 1;
            double avg = s / len;
            if (opt == 2) {
                cout << avg << '\n';
            } else {
                // 方差 = E(x^2) - (E(x))^2
                cout << s2 / len - avg * avg << '\n';
            }
        }
    }

    return 0;
}

brute.cpp 直接维护数组：操作 1 逐项加，操作 2、3 暴力扫描区间求和与平方和，单次操作 $O(n)$ ，总复杂度 $O(nm)$ ，无法通过 $10^5$ 的数据。

关键观察是把方差改写成一阶矩与二阶矩的形式。设 $x$ 为在区间 $[l,r]$ 内均匀随机取值的变量，则 $E(x) = \overline A = \frac{\sum a_i}{len}$ ， $E(x^2) = \frac{\sum a_i^2}{len}$ ，由 $\mathrm{Var}(x) = E(x^2) - (E(x))^2$ ：

s^2 = \frac{1}{len}\sum(a_i - \overline A)^2 = \frac{\sum a_i^2}{len} - \left(\frac{\sum a_i}{len}\right)^2 = E(x^2) - (E(x))^2

这样查询只依赖区间的两个可合并量：和 $S = \sum a_i$ 与平方和 $Q = \sum a_i^2$ 。其中 $(E(x))^2 = \left(\frac{S}{len}\right)^2$ 由 $S$ 直接得到，好求；真正的难点在 $E(x^2)$ 里的平方和 $Q$ ——区间加 $k$ 后每个元素都变了， $Q = \sum a_i^2$ 该怎么更新？难道要逐项重算平方吗？

答案是不需要。对区间整段加 $k$ 时（区间长度 $len$ ），把 $Q'$ 直接展开：

S' = S + len \cdot k,\qquad Q' = \sum(a_i + k)^2 = \sum(a_i^2 + 2ka_i + k^2) = Q + 2k \cdot S + len \cdot k^2

$Q'$ 只由旧的 $S$ 与 $Q$ 算出，不需要任何逐项信息，所以整段加法可以被节点懒标记完整吸收——这就是区间加线段树的封闭性：节点只维护 $(S, Q, lazy)$ ，完全覆盖时整段更新，递归进入孩子前下传标记。

另一个必须满足的是合并：push_up 时父节点要由左右子树拼出， $S = S_L + S_R$ ， $Q = Q_L + Q_R$ ，两者都是普通加法，结合律显然成立，合并结果与区间如何分割无关，所以线段树任何一层把区间拆成两半再合并都不影响正确性。

以样例为例，三次询问对应的矩如下：

步骤	操作	区间	和 $S$	平方和 $Q$	输出
1	`2 1 4`	$[1,4]$	$12$	$46$	`3.0000`
2	`3 1 5`	$[1,5]$	$15$	$55$	`2.0000`
5	`3 1 5`	$[1,5]$	$15$	$49$	`0.8000`

观察第一行：平均数是 $12/4 = 3$ ；第二行方差 $= 55/5 - (15/5)^2 = 11 - 9 = 2$ ，正是 $E(x^2) - (E(x))^2$ 。步骤 3、4 两次区间加后，平方和由 $55$ 变为 $49$ （每一步都由 $Q' = Q + 2kS + len\cdot k^2$ 逐节点更新），第三行方差 $= 49/5 - 9 = 0.8$ ，与样例输出一致。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:10
 * update_at: 2026-08-15 22:00
 */
// main.cpp：P1471 正式解，线段树懒标记同时维护区间和与平方和，
// 支持区间加实数、查询区间平均值与方差，单次操作 O(log n)。
#include <bits/stdc++.h>
using namespace std;

// 区间加 + 区间和与平方和线段树（懒标记）
struct SegmentTreeRangeAdd {
    using T = double;

    // 线段树节点：s 为区间和，q 为平方和，lazy 为待下传的加法值
    struct Node {
        T s = 0;        // 当前区间的真实区间和 Σa[i]
        T q = 0;        // 当前区间的真实平方和 Σa[i]^2
        T lazy = 0;     // 待下传的加法值

        // 合并两个孩子：和相加、平方和相加，合并结果不携带懒标记
        Node operator+(const Node &other) const {
            return Node{s + other.s, q + other.q};
        }
    };

    // 左儿子 / 右儿子的节点编号
    static int lson(int p) { return p << 1; }
    static int rson(int p) { return p << 1 | 1; }

    // 区间 [l, r] 的中点
    static int mid(int l, int r) { return (l + r) >> 1; }

    int n = 0;              // 区间大小
    vector<Node> tree;      // 线段树数组

    SegmentTreeRangeAdd(int n = 0) {
        init(n);
    }

    void init(int size) {
        n = size;
        tree.assign(n * 4 + 5, Node{});
    }

    // 上推：用两个孩子合并出当前节点
    void push_up(int p) {
        tree[p] = tree[lson(p)] + tree[rson(p)];
    }

    // 把节点 p 的整个区间 [l, r] 的每个元素都加上 val。
    // 平方和：Σ(a[i]+val)^2 = Σa[i]^2 + 2*val*Σa[i] + len*val^2，
    // 注意先使用旧的 s 更新 q，再更新 s。
    void apply(int p, int l, int r, T val) {
        int len = r - l + 1;
        tree[p].q += 2 * val * tree[p].s + val * val * len;
        tree[p].s += val * len;
        tree[p].lazy += val;
    }

    // 下推：把节点 p 的加法懒标记传给两个孩子
    void push_down(int p, int l, int r) {
        if (tree[p].lazy == 0 || l == r) return;

        int m = mid(l, r);
        apply(lson(p), l, m, tree[p].lazy);
        apply(rson(p), m + 1, r, tree[p].lazy);
        tree[p].lazy = 0;
    }

    // 用数组 a 建树（下标从 1 开始）
    void build(const vector<T> &a, int l, int r, int p = 1) {
        if (l == r) {
            tree[p].s = a[l];
            tree[p].q = a[l] * a[l];
            return;
        }
        int m = mid(l, r);
        build(a, l, m, lson(p));
        build(a, m + 1, r, rson(p));
        push_up(p);
    }

    // 区间加：把 [ql, qr] 的每个元素都加上 val
    void add_range(int ql, int qr, T val, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) {
            apply(p, l, r, val);
            return;
        }

        push_down(p, l, r);
        int m = mid(l, r);
        if (ql <= m) add_range(ql, qr, val, l, m, lson(p));
        if (qr > m) add_range(ql, qr, val, m + 1, r, rson(p));
        push_up(p);
    }

    // 区间查询：返回 [ql, qr] 的和与平方和
    Node query(int ql, int qr, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) return tree[p];

        push_down(p, l, r);
        int m = mid(l, r);
        Node answer;
        if (ql <= m) answer = answer + query(ql, qr, l, m, lson(p));
        if (qr > m) answer = answer + query(ql, qr, m + 1, r, rson(p));
        return answer;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<double> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    SegmentTreeRangeAdd seg(n);
    seg.build(a, 1, n);

    cout << fixed << setprecision(4); // 输出统一保留 4 位小数

    while (m--) {
        int opt, l, r;
        cin >> opt >> l >> r;
        if (opt == 1) {
            double k;
            cin >> k;
            seg.add_range(l, r, k, 1, n);
        } else {
            auto res = seg.query(l, r, 1, n);
            double len = r - l + 1;
            double avg = res.s / len;   // 平均值 = Σa / len
            if (opt == 2) {
                cout << avg << '\n';
            } else {
                // 方差 = E(x^2) - (E(x))^2 = Σa^2/len - (Σa/len)^2
                cout << res.q / len - avg * avg << '\n';
            }
        }
    }

    return 0;
}

复杂度

时间：建树 $O(n)$ ，区间加与两种查询各 $O(\log n)$ ，总 $O(n + m \log n)$ 。
空间：sum、sum2、lazy 三个 $4n$ 数组， $O(n)$ 。

总结

遇到"区间修改 + 方差查询"，套路是先把方差改写成一阶矩与二阶矩的组合，让查询只依赖两个满足合并律的量；再看区间加在这两个量上的更新是否封闭（ $Q'$ 由旧 $S$ 、 $Q$ 直接算出），封闭就能套懒标记线段树。rbook 的《线段树：区间赋值与区间查询》讲解了本解使用的懒标记骨架（apply / push / pull），本题把"赋值"语义换成"加法"并多维护一个平方和字段即可。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24朴素模拟（brute.cpp）
  区间加逐项 a[i] += k，查询暴力扫描区间求平均/方差   O(n) 每次操作
        |
        | 瓶颈：逐项访问区间，m 次操作 O(n*m) 太大
        v
关键观察（改写方差）
  s^2 = E(x^2) - (E(x))^2
  查询只依赖两个可合并量：和 S = Σa_i，平方和 Q = Σa_i^2
        |
        | 整段加 k 是否封闭？
        v
封闭性验证
  S' = S + len*k
  Q' = Q + 2*k*S + len*k^2     只依赖旧 (S, Q)，不需要逐项信息
        |
        v
懒标记线段树（main.cpp）
  节点维护 (sum, sum2, lazy)
  完全覆盖：apply 整段更新并叠加标记
  进入孩子前：push 下传标记，回溯 pull 重新合并
  查询：平均数 = S/len，方差 = Q/len - (S/len)^2
        |
        v
复杂度 O((n + m) log n)，空间 O(n)

图中四层对应"暴力慢在哪"“方差如何退化成一阶、二阶矩”“整段加为何能被节点吸收”“线段树如何把修改压缩到 $O(\log n)$ 个节点”。核心是把"逐项加 + 逐项求平方差"的困难，转换成"两个可合并矩的封闭更新"，难度就从逐项模拟降为懒标记区间维护。

P1471 方差

题目背景

滚粗了的 HansBug 在收拾旧数学书，然而他发现了什么奇妙的东西。

题目描述

蒟蒻 HansBug 在一本数学书里面发现了一个神奇的数列，包含 $N$ 个实数。他想算算这个数列的平均数和方差。

输入格式

第一行包含两个正整数 $N,M$ ，分别表示数列中实数的个数和操作的个数。

第二行包含 $N$ 个实数，其中第 $i$ 个实数表示数列的第 $i$ 项。

接下来 $M$ 行，每行为一条操作，格式为以下三种之一：

操作 $1$ ：1 x y k ，表示将第 $x$ 到第 $y$ 项每项加上 $k$ ， $k$ 为一实数。
操作 $2$ ：2 x y ，表示求出第 $x$ 到第 $y$ 项这一子数列的平均数。
操作 $3$ ：3 x y ，表示求出第 $x$ 到第 $y$ 项这一子数列的方差。

输出格式

输出包含若干行，每行为一个实数，即依次为每一次操作 $2$ 或操作 $3$ 所得的结果（所有结果四舍五入保留 $4$ 位小数）。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

关于方差：对于一个有 $n$ 项的数列 $A$ ，其方差 $s^2$ 定义如下：

s^2=\frac{1}{n}\sum\limits_{i=1}^n\left(A_i-\overline A\right)^2

其中

\overline A

表示数列

A

的平均数，

A_i

表示数列

A

的第

i

项。

样例说明：

操作步骤	输入内容	操作要求	数列	输出结果	说明
$0$	-	-	`1 5 4 2 3`	-	-
$1$	`2 1 4`	求 $\left[1,4\right]$ 内所有数字的平均数	`1 5 4 2 3`	`3.0000`	平均数 $=\left(1+5+4+2\right)\div 4=3.0000$
$2$	`3 1 5`	求 $\left[1,5\right]$ 内所有数字的方差	`1 5 4 2 3`	`2.0000`	平均数 $=\left(1+5+4+2+3\right)\div 5=3$ ，方差 $=\left(\left(1-3\right)^2+\left(5-3\right)^2+\left(4-3\right)^2+\left(2-3\right)^2+\left(3-3\right)^2\right)\div 5=2.0000$
$3$	`1 1 1 1`	将 $\left[1,1\right]$ 内所有数字加 $1$	`2 5 4 2 3`	-	-
$4$	`1 2 2 -1`	将 $\left[2,2\right]$ 内所有数字加 $-1$	`2 4 4 2 3`	-	-
$5$	`3 1 5`	求 $\left[1,5\right]$ 内所有数字的方差	`2 4 4 2 3`	`0.8000`	平均数 $=\left(2+4+4+2+3\right)\div 5=3$ ，方差 $=\left(\left(2-3\right)^2+\left(4-3\right)^2+\left(4-3\right)^2+\left(2-3\right)^2+\left(3-3\right)^2\right)\div 5=0.8000$

数据规模：

数据点	$N$	$M$	备注
$1\sim3$	$N\le 8$	$M\le 15$	-
$4\sim7$	$N\le 10^5$	$M\le 10^5$	不包含操作 $3$
$8\sim10$	$N\le 10^5$	$M\le 10^5$	-

保证原数列和输入的所有 $k$ 均为 $[-100,100]$ 范围内的实数。

方差

目录

形式化题目

思路

代码

复杂度

总结

图示解析