C39 线段树+数学 P5142 区间方差

#include<cstdio>
using namespace std;

typedef long long LL;
const int N=100005,mod=1e9+7;
#define ls u<<1
#define rs u<<1|1#define sqr(x) ((LL)(x)*(x)%mod)
int n,m,a[N];
int L[N<<2],R[N<<2],s1[N<<2],s2[N<<2];
//s1:区间和, s2:区间平方和平

int qpow(int a){ //快速幂
  int s=1, b=mod-2;
  while(b){
    if(b&1) s=(LL)s*a%mod;
    a=(LL)a*a%mod;
    b>>=1;
  }
  return s;
}
void pushup(int u){ //上传
  s1[u]=(s1[ls]+s1[rs])%mod;
  s2[u]=(s2[ls]+s2[rs])%mod;
}
void build(int u,int l,int r){ //建树
  L[u]=l;R[u]=r;
  s1[u]=a[l];s2[u]=sqr(a[l]);
  if(l==r) return;
  int m=(l+r)>>1;
  build(ls,l,m);
  build(rs,m+1,r);
  pushup(u);
}
void change(int u,int k,int v){ //点修if(L[u]==R[u]){
    s1[u]=v;
    s2[u]=sqr(v);
    return;
  }
  int m=(L[u]+R[u])>>1;
  if(k<=m) change(ls,k,v);
  else change(rs,k,v);
  pushup(u);
}
int q1(int u,int x,int y){ //区间和
  if(x<=L[u] && R[u]<=y) return s1[u];
  int m=(L[u]+R[u])>>1;
  if(y<=m) return q1(ls,x,y);
  if(x>m) return q1(rs,x,y);
  return (q1(ls,x,m)+q1(rs,m+1,y))%mod;
}
int q2(int u,int x,int y){ //区间平方和
  if(x<=L[u] && R[u]<=y) return s2[u];
  int m=(L[u]+R[u])>>1;if(y<=m) return q2(ls,x,y);
  if(x>m) return q2(rs,x,y);
  return (q2(ls,x,m)+q2(rs,m+1,y))%mod;
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
  build(1,1,n);
  
  int op,x,y,s1,s2,inv,ave,ans;
  while(m--){
    scanf("%d%d%d",&op,&x,&y);
    if(op==1) change(1,x,y);
    else{
      s1=q1(1,x,y);       //区间和
      s2=q2(1,x,y);       //区间平方和平
      inv=qpow(y-x+1);    //区间长度的逆元
      ave=(LL)s1*inv%mod; //区间算术平均数
      ans=(LL)s2*inv%mod-(LL)ave*ave%mod;
      ans=(ans%mod+mod)%mod;
      printf("%d\n",ans);
    }
  }
  return 0;
}