洛谷P5142 区间方差题解

题意：

对于一个长度为 \(n\) 的序列 \(a_1,a_2,a_3\cdots a_n\)，我们定义它的平均数 \(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\) 的序列 \(a_1,a_2\cdots a_n\)。你需要支持两种操作。每种操作的格式为 c x y。

若 \(c=1\)，为修改操作，代表将 \(a_x\) 赋值为 \(y\)。

若 \(c=2\)，为查询操作，代表查询 \(a_x\) 到 \(a_y\) 的方差。

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

对于 \(100\%\) 的数据，\(1\leq n,m\leq 1\times 10^5\)，\(1\leq a_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\)。

方差有个更快的公式 \[ \dfrac{\sum_{i=1}^{n} a_i^2}{n} - a^2 \] 推导过程很简单，只要把那个 \((a-a_i)^2\) 展开就好了

这样我们就只要维护两个数组 \[ \begin{aligned} S_1 &= \sum_{i=l}^{r}a_i \\S_2&= \sum_{i=l}^{r}a_i^2 \end{aligned} \] 单点修改都不需要懒标记，很水吧

不过这个取模除法，所以要算个逆元

因为 \(10^9+7\) 是个质数，而且 \(a_i \le 10^9\)

所以直接用费马小定理那个东西求个逆元就好了

时间复杂度 \(O(m \log (na_i))\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e5+15)

const int p=1e9+7;
int n,Q,a[N],sum1[N<<2],sum2[N<<2];
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
int qpow(int a,int b)
{
    int ans=1,base=a%p;
    while(b)
    {
        if(b&1) ans=ans*base%p;
        base=base*base%p;
        b>>=1;
    }
    return ans;
}
int inv(int x){return qpow(x,p-2);}
void push_up(int at)
{
    sum1[at]=(sum1[ls(at)]+sum1[rs(at)])%p;
    sum2[at]=(sum2[ls(at)]+sum2[rs(at)])%p;
}
void build(int l,int r,int at)
{
    if(l==r)
    {
        sum1[at]=a[l]%p;
        sum2[at]=a[l]%p*a[l]%p;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls(at));
    build(mid+1,r,rs(at));
    push_up(at);
}
void modify(int x,int l,int r,int k,int at)
{
    if(l==r)
    {
        sum1[at]=k%p;
        sum2[at]=k%p*k%p;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)modify(x,l,mid,k,ls(at));
    else modify(x,mid+1,r,k,rs(at));
    push_up(at);
}
int query1(int nl,int nr,int l,int r,int at)
{
    if(nl<=l&&r<=nr) return sum1[at]%p;
    int mid=(l+r)>>1;
    int res=0;
    if(nl<=mid) res=(res+query1(nl,nr,l,mid,ls(at)))%p;
    if(nr>mid) res=(res+query1(nl,nr,mid+1,r,rs(at)))%p;
    return res;
}
int query2(int nl,int nr,int l,int r,int at)
{
    if(nl<=l&&r<=nr) return sum2[at]%p;
    int mid=(l+r)>>1;
    int res=0;
    if(nl<=mid) res=(res+query2(nl,nr,l,mid,ls(at)))%p;
    if(nr>mid) res=(res+query2(nl,nr,mid+1,r,rs(at)))%p;
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n);read(Q);
    for(int i=1; i<=n; i++)
        read(a[i]);
    build(1,n,1);
    for(int op,x,y; Q--; )
    {
        read(op); read(x); read(y);
        if(op==1) modify(x,1,n,y,1);
        else
        {
            int t1=query2(x,y,1,n,1);
            int t2=query1(x,y,1,n,1);
            int t3=inv(y-x+1);
            t1=t1%p*t3%p;
            t2=t2%p*t3%p;t2=t2%p*t2%p;
            write(((t1-t2)%p+p)%p);pc('\n');
        }
    }
    return 0;
}