lp1471 方差

大力上一个线段树。
将方差展开为由区间平方的和与区间和两项构成的多项式，然后维护区间平方的和与区间和。
具体来说，通过将二项式展开可以得到公式：
$$ \sum_{i=l}^{r}(a_{i}+k)^2=\sum_{i=l}^{r}a_{i}^2+\sum_{i=l}^{r}*k*2+(r-l+1)*k^2 $$
套用这个公式，就可以用与维护普通的线段树相似的方法来维护这个数据结构。

#include<iostream>
#include<cstdio>
using namespace std;
#define LEN (R-L+1)
#define MID ((L+R)>>1)
#define LLEN (MID-L+1)
#define RLEN (R-MID)
#define LS (X<<1)
#define RS (X<<1|1)
struct data{
	double sm;
	double sm2;
	double lzy;
}tr[270005];//262141
inline void rnw(int X,int Len,double K){
	tr[X].sm2+=(tr[X].sm*2*K+K*K*Len);
	tr[X].sm+=(K*Len);
	tr[X].lzy+=K;
}
inline void pshd(int X,int L,int R){
	rnw(LS,LLEN,tr[X].lzy);rnw(RS,RLEN,tr[X].lzy);
	tr[X].lzy=0;
}
inline void updt(int X){
	tr[X].sm2=tr[LS].sm2+tr[RS].sm2;
	tr[X].sm=tr[LS].sm+tr[RS].sm;
}
inline void add(int X,int L,int R,int A,int B,double K){
	if(L>=A&&R<=B){
		rnw(X,LEN,K);
		return;
	}
	pshd(X,L,R);
	if(A<=MID){
		add(LS,L,MID,A,B,K);
	}
	if(B>MID){
		add(RS,MID+1,R,A,B,K);
	}
	updt(X);
}
inline double qrySm(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X].sm;
	}
	pshd(X,L,R);
	double rt=0;
	if(A<=MID){
		rt+=qrySm(LS,L,MID,A,B);
	}
	if(B>MID){
		rt+=qrySm(RS,MID+1,R,A,B);
	}
	return rt;
}
inline double qrySm2(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X].sm2;
	}
	pshd(X,L,R);
	double rt=0;
	if(A<=MID){
		rt+=qrySm2(LS,L,MID,A,B);
	}
	if(B>MID){
		rt+=qrySm2(RS,MID+1,R,A,B);
	}
	return rt;
}
int n,m;
double a[100005];
inline void build(int X,int L,int R){
	if(L==R){
		tr[X].sm=a[L];
		tr[X].sm2=a[L]*a[R];
		return;
	}
	build(LS,L,MID);build(RS,MID+1,R);
	updt(X);
}
void init(){
	scanf("%d%d",&n,&m);
	double x;
	for(int i=1;i<=n;++i){
		scanf("%lf",a+i);
	}
	build(1,1,n);
	int op,l,r;
	while(m--){
		scanf("%d%d%d",&op,&l,&r);
		if(op==1){
			scanf("%lf",&x);
			add(1,1,n,l,r,x);
		}else if(op==2){
			printf("%.4lf\n",qrySm(1,1,n,l,r)/(r-l+1));
		}else{
			x=qrySm(1,1,n,l,r);
			printf("%.4lf\n",(qrySm2(1,1,n,l,r)-x*x/(r-l+1))/(r-l+1));
		}
	}
}
int main(){
	init();
	return 0;
}