P1471 方差

算法

线段树
数学推导（平均数，方差）

思路

区间操作，很容易想到线段树。但是方差不好合并，考虑拆解：

\large \begin{aligned} s^2 &= \frac{1}{n} \sum_{i = 1}^{n} (A_i - \overline A)^2 \\ &= \frac{1}{n} \sum_{i = 1}^{n} (A_i^2 - 2 \cdot A_i^2 \cdot \overline A + \overline A^2) \\ &= \frac{1}{n} (\sum_{i = 1}^{n} A_i^2 - \sum_{i = 1}^{n} 2 \cdot A_i^2 \cdot \overline A + \sum_{i = 1}^{n} \overline A^2) \\ &= \frac{1}{n} (\sum_{i = 1}^{n} A_i^2 - 2 \cdot \overline A \cdot \sum_{i = 1}^{n} A_i + n \overline A^2) \end{aligned}

所以我们只需要维护区间和 $sum$ ，区间平方和 $sum\_square$ 就可以了。对于区间加的操作，有如下推导（记 $sum2$ 为区间平方和）：

\large \begin{aligned} sum2^{\prime} &= \sum_{i = 1}^{n} (A_i + val)^2 \\ &= \sum_{i = 1}^{n} (A_i^2 + 2 \cdot A_i \cdot val + val^2) \\ &= \sum_{i = 1}^{n} A_i^2 + \sum_{i = 1}^{n} 2 \cdot A_i \cdot val + \sum_{i = 1}^{n} val^2 \\ &= sum2 + 2 \cdot val \cdot \sum_{i = 1}^{n} + n \cdot val^2 \end{aligned}

然后我们就做完了。

代码

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
constexpr int N = 1e5 + 5;
6
long double arr[N], k;
7
int n, m, op_type, l, r;
8

9
struct SegmentTree {
10
  public:
11
  struct Node {
12
    int l, r;
13
    long double sum_square, sum, add;
14
  };
15

16
  Node tr[N << 2];
17

18
  void lazy(int k, long double value) {
19
    tr[k].sum_square += tr[k].sum * 2 * value + (tr[k].r - tr[k].l + 1) * value * value;
20
    tr[k].sum += (tr[k].r - tr[k].l + 1) * value;
21
    tr[k].add += value;
22
  }
23

24
  void push_up(int k) {
25
    int lc = k << 1, rc = k << 1 | 1;
26
    tr[k].sum_square = tr[lc].sum_square + tr[rc].sum_square;
27
    tr[k].sum = tr[lc].sum + tr[rc].sum;
28
  }
29

30
  void push_down(int k) {
31
    if (tr[k].add == 0) {
32
      return void();
33
    }
34

35
    int lc = k << 1, rc = k << 1 | 1;
36
    lazy(lc, tr[k].add);
37
    lazy(rc, tr[k].add);
38

39
    // ! 注意下传懒标记要清空。
40
    tr[k].add = 0;
41
  }
42

43
  void build_tree(int k, int l, int r) {
44
    tr[k].l = l, tr[k].r = r;
45
    tr[k].sum = tr[k].sum_square = tr[k].add = 0;
46

47
    if (tr[k].l == tr[k].r) {
48
      tr[k].sum = arr[l];
49
      tr[k].sum_square = arr[l] * arr[l];
50
      return void();
51
    }
52

53
    int mid = (tr[k].l + tr[k].r) >> 1;
54
    int lc = k << 1, rc = k << 1 | 1;
55

56
    build_tree(lc, l, mid);
57
    build_tree(rc, mid + 1, r);
58

59
    push_up(k);
60
  }
61

62
  void modify(int k, int l, int r, long double value) {
63
    if (tr[k].l >= l && tr[k].r <= r) {
64
      lazy(k, value);
65
      return void();
66
    }
67

68
    push_down(k);
69

70
    int mid = (tr[k].l + tr[k].r) >> 1;
71
    int lc = k << 1, rc = k << 1 | 1;
72

73
    if (r <= mid) {
74
      modify(lc, l, r, value);
75
    } else if (l > mid) {
76
      modify(rc, l, r, value);
77
    } else {
78
      modify(lc, l, mid, value);
79
      modify(rc, mid + 1, r, value);
80
    }
81

82
    push_up(k);
83
  }
84

85
  long double __query_sum(int k, int l, int r) {
86
    if (tr[k].l >= l && tr[k].r <= r) {
87
      return tr[k].sum;
88
    }
89

90
    push_down(k);
91

92
    int mid = (tr[k].l + tr[k].r) >> 1;
93
    int lc = k << 1, rc = k << 1 | 1;
94

95
    if (r <= mid) {
96
      return __query_sum(lc, l, r);
97
    } else if (l > mid) {
98
      return __query_sum(rc, l, r);
99
    } else {
100
      return __query_sum(lc, l, mid) + __query_sum(rc, mid + 1, r);
101
    }
102
  }
103

104
  long double __query_sum_square(int k, int l, int r) {
105
    if (tr[k].l >= l && tr[k].r <= r) {
106
      return tr[k].sum_square;
107
    }
108

109
    push_down(k);
110

111
    int mid = (tr[k].l + tr[k].r) >> 1;
112
    int lc = k << 1, rc = k << 1 | 1;
113

114
    if (r <= mid) {
115
      return __query_sum_square(lc, l, r);
116
    } else if (l > mid) {
117
      return __query_sum_square(rc, l, r);
118
    } else {
119
      return __query_sum_square(lc, l, mid) + __query_sum_square(rc, mid + 1, r);
120
    }
121
  }
122

123
  long double query_average(int l, int r) {
124
    long double sum = __query_sum(1, l, r);
125
    return sum / (long double) (r - l + 1);
126
  }
127

128
  long double query_variance(int l, int r) {
129
    long double average = query_average(l, r);
130
    long double sum = __query_sum(1, l, r);
131
    long double sum_square = __query_sum_square(1, l, r);
132
    int length = r - l + 1;
133

134
    // cout << average << " " << sum << " " << sum_square << '\n';
135

136
    return (sum_square - 2 * average * sum + length * average * average) / (long double) length;
137
  }
138
} segment_tree;
139

140
int main() {
141
  ios::sync_with_stdio(false);
142
  cin.tie(nullptr);
143
  cout.tie(nullptr);
144

145
  cin >> n >> m;
146

147
  for (int i = 1; i <= n; i ++) {
148
    cin >> arr[i];
149
  }
150

151
  segment_tree.build_tree(1, 1, n);
152

153
  while (m --) {
154
    cin >> op_type >> l >> r;
155

156
    if (op_type == 1) {
157
      cin >> k;
158
      segment_tree.modify(1, l, r, k);
159
    } else if (op_type == 2) {
160
      long double result = segment_tree.query_average(l, r);
161
      result = round(result * 10000) / (long double) 10000;
162

163
      cout << setiosflags(ios::fixed) << setprecision(4) << result << '\n';
164
    } else if (op_type == 3) {
165
      long double result = segment_tree.query_variance(l, r);
166
      result = round(result * 10000) / (long double) 10000;
167

168
      cout << setiosflags(ios::fixed) << setprecision(4) << result << '\n';
169
    }
170
  }
171

172
  return 0;
173
}