给定数列，维护区间平均数和区间方差，并支持区间修改。\(n\leq10^5,m\leq10^5\)。
线段树维护平均数比较简单，重点在于如何维护方差。
具体公式参考了这篇题解，就不详细展开，推出来以后就变成简单的线段树维护问题。
#include<bits/stdc++.h>
using namespace std;
struct node{
double sum,tag,pow_sum;
int l,r;
};
struct ST{
node nd[400005];
double a[400005];
inline int ls(int p){
return p<<1;
}
inline int rs(int p){
return p<<1|1;
}
inline void push_up(int p){
nd[p].sum=nd[ls(p)].sum+nd[rs(p)].sum;
nd[p].pow_sum=nd[ls(p)].pow_sum+nd[rs(p)].pow_sum;
return;
}
inline void add_tag(int p,double k){
int l=nd[p].l;
int r=nd[p].r;
nd[p].tag+=k;
nd[p].pow_sum+=2*k*(nd[p].sum)+(r-l+1)*k*k;
nd[p].sum+=k*(double)(r-l+1);
return;
}
void push_down(int p){
add_tag(ls(p),nd[p].tag);
add_tag(rs(p),nd[p].tag);
nd[p].tag=0.0;
return;
}
void build(int l,int r,int p){
nd[p].l=l;
nd[p].r=r;
if(l==r){
nd[p].sum=a[l];
nd[p].pow_sum=a[l]*a[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,ls(p));
build(mid+1,r,rs(p));
push_up(p);
return;
}
void updata(int p,int ql,int qr,double k){
int l=nd[p].l;
int r=nd[p].r;
if(ql<=l && r<=qr){
add_tag(p,k);
return;
}
push_down(p);
int mid=(l+r)>>1;
if(ql<=mid)
updata(ls(p),ql,qr,k);
if(qr>mid)
updata(rs(p),ql,qr,k);
push_up(p);
return;
}
double get_1(int p,int ql,int qr){
int l=nd[p].l;
int r=nd[p].r;
if(ql<=l && r<=qr){
return nd[p].sum;
}
push_down(p);
int mid=(l+r)>>1;
double ret=0.0;
if(ql<=mid)
ret+=get_1(ls(p),ql,qr);
if(qr>mid)
ret+=get_1(rs(p),ql,qr);
return ret;
}
double get_2(int p,int ql,int qr){
int l=nd[p].l;
int r=nd[p].r;
if(ql<=l && r<=qr){
return nd[p].pow_sum;
}
push_down(p);
int mid=(l+r)>>1;
double ret=0.0;
if(ql<=mid)
ret+=get_2(ls(p),ql,qr);
if(qr>mid)
ret+=get_2(rs(p),ql,qr);
return ret;
}
double query_1(int ql,int qr){
return get_1(1,ql,qr)/(double)(qr-ql+1);
}
double query_2(int ql,int qr){
double q1=query_1(ql,qr);
return get_2(1,ql,qr)/(qr-ql+1)-q1*q1;
}
}S;
int n,m;
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%lf",&S.a[i]);
S.build(1,n,1);
while(m){
m--;
int op,x,y;
scanf("%d %d %d",&op,&x,&y);
switch(op){
case 1:{
double k;
scanf("%lf",&k);
S.updata(1,x,y,k);
break;
}
case 2:{
printf("%.4lf\n",S.query_1(x,y));
break;
}
case 3:{
printf("%.4lf\n",S.query_2(x,y));
break;
}
}
}
return 0;
}