本文共 3408 字，大约阅读时间需要 11 分钟。

简述题意

给一段序列，支持区间求方差，单点修改

前置芝士

• 线段树/树状数组/分块
• 逆元
• 推式子

Solution

题目中已经给出了方差的求法，我们这里设 \(len\) 表示要求的区间长度：

看上去不好维护，让我们化简试试：

直接利用乘法分配律将其分开：

很简单的昂，把无关项提出来,得到：

因为 \(\overline{a} = \frac{1}{len} \sum_{i = l}^{r} a_i\)，所以继续化简可以得到：

然后直接pia的一下，把线段树扔上去，维护个区间和和区间平方和，连Push_down都不需要写，就做完了。

但是！！

我们知道方差经常是分数形式，并且这还是在模意义下。

那么求出分母的逆元就好了，具体原理见。

求逆元有两种方法（我们定义 \(a\) 的逆元为 \(a^{-1}\)）：

• 费马小定理：\(a^{-1} = a^{p - 2} \bmod {p}\)；

• 线性求逆元递推公式：

  $inv_i = (p - \frac{p}{i}) \times inv_{p \bmod i} \bmod p $，证明的话可以看。

Tips:

• 记得开 long long；
• 取模要彻底。

剩下的看代码吧。

Code

/*Work by: Suzt_ilymicsProblem: P5142 区间方差Knowledge: 线段树Time: O(nlogn)*/#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #define LL long long#define int long long#define orz cout<<"lkp AK IOI!"<
        
         << 1) + (s << 3) + ch - '0' , ch = getchar(); return f ? -s : s;}namespace Seg{ #define lson i << 1 #define rson i << 1 | 1 struct Tree{ int val, sum; }tree[MAXN << 2]; void Push_up(int i) { // 更新 tree[i].val = (tree[lson].val + tree[rson].val) % mod; tree[i].sum = (tree[lson].sum + tree[rson].sum) % mod; } void Build(int i, int l, int r) { // 建树 if(l == r) { tree[i].val = a[l] % mod, tree[i].sum = a[l] * a[l] % mod; return ; } int mid = (l + r) >> 1; Build(lson, l, mid), Build(rson, mid + 1, r); Push_up(i); } void Modify(int i, int l, int r, int L, int R, int val_) { // 单点修改，粘的模板所以写的区间修改的形式 if(L <= l && r <= R) { tree[i].val = val_ % mod, tree[i].sum = val_ * val_ % mod; return ; } int mid = (l + r) >> 1; if(mid >= L) Modify(lson, l, mid, L, R, val_); if(mid < R) Modify(rson, mid + 1, r, L, R, val_); Push_up(i); } int Query1(int i, int l, int r, int L, int R) { // 区间和 if(L <= l && r <= R) return tree[i].val; int mid = (l + r) >> 1, ans = 0; if(mid >= L) ans += Query1(lson, l, mid, L, R); if(mid < R) ans += Query1(rson, mid + 1, r, L, R); return ans % mod; } int Query2(int i, int l, int r, int L, int R) { // 区间平方和 if(L <= l && r <= R) return tree[i].sum; int mid = (l + r) >> 1, ans = 0; if(mid >= L) ans += Query2(lson, l, mid, L, R); if(mid < R) ans += Query2(rson, mid + 1, r, L, R); return ans % mod; }}void Init() { inv[0] = inv[1] = 1; // 线性求逆元，注意初始化 for(int i = 2; i <= n; ++i) inv[i] = (mod - mod / i) * inv[mod % i] % mod;}int Quick_Pow(int x, int p, int mod) { // 快速幂（然而没用到 int res = 1; while(p) { if(p & 1) res = res * x % mod; x = x * x % mod; p >>= 1; } return res;}signed main(){ n = read(), m = read(); Init(); for(int i = 1; i <= n; ++i) a[i] = read(); Seg::Build(1, 1, n); for(int i = 1, opt, l, r; i <= m; ++i) { opt = read(), l = read(), r = read(); if(opt == 1) Seg::Modify(1, 1, n, l, l, r); else { int len = r - l + 1; int sum1 = Seg::Query1(1, 1, n, l, r) * inv[len] % mod; int sum2 = Seg::Query2(1, 1, n, l, r) * inv[len] % mod; printf("%lld\n", (sum2 - sum1 * sum1 % mod + mod) % mod); } } return 0;}