洛谷 P1471 方差（线段树+数学）

 

对于操作 1，2 应该很简单可以实现，但是操作 3，该如何实现，一定是要经过转化的

，利用线段树，很容易求得任意区间的和，现在只剩下求    这一块的值为多少即可

emmmmm，以我现在的数学能力是没有办法在化简了，但是我们可以用线段树再来维护一下这个值

 

当区间 +k 操作时，那么有   

这样区间平方和也变得可以维护了

const int N=1e5+5;

    int i,j,k;
    int n,m;
    double a[N];  
    struct Node
	{
		int l,r;
		double sum,sqr;
		double lazy;
		void update(double x)
		{
			sqr+=2*x*sum+(r-l+1)*x*x;
			sum+=(r-l+1)*x;
			lazy+=x;
		}
		#define lson id<<1
		#define rson id<<1|1
	}t[N<<2];
	double sum,sqr;

void push_up(int id)
{
	t[id].sum=t[lson].sum+t[rson].sum;
	t[id].sqr=t[lson].sqr+t[rson].sqr;
}

void push_down(int id)
{
	double x=t[id].lazy;
	if(x){
		t[lson].update(x);
		t[rson].update(x);
		t[id].lazy=0;
	}
}

void build(int l,int r,int id)
{
	t[id].l=l,t[id].r=r;
	t[id].lazy=0;
	if(l==r) t[id].sum=a[l],t[id].sqr=a[l]*a[l];
	else{
		int mid=l+r>>1;
		build(l,mid,lson);
		build(mid+1,r,rson);
		push_up(id);
	}
}

void update(int l,int r,double val,int id)
{
	int L=t[id].l,R=t[id].r;
	if(L>=l && r>=R) t[id].update(val);
	else{
		int mid=L+R>>1;
		push_down(id);
		if(mid>=l) update(l,r,val,lson);
		if(r>=mid+1) update(l,r,val,rson);
		push_up(id);
	}
}

void query(int l,int r,int id,bool flag)
{
	int L=t[id].l,R=t[id].r;
	if(L>=l && r>=R){
		if(flag) sum+=t[id].sum,sqr+=t[id].sqr;
		else sum+=t[id].sum;
	} else{
		int mid=L+R>>1;
		push_down(id);
		if(mid>=l) query(l,r,lson,flag);
		if(r>=mid+1) query(l,r,rson,flag);
		push_up(id);
	}
}

int main()
{
    //IOS;
    while(~sdd(n,m)){
		for(int i=1;i<=n;i++) sf(a[i]);
		build(1,n,1);
		int opt,x,y;double k;
		while(m--){
			sddd(opt,x,y);
			if(opt==1){
				sf(k);
				update(x,y,k,1);
			} else if(opt==2){
				sum=0;
				query(x,y,1,0);
				printf("%.4lf\n",sum/(y-x+1));
			} else{
				sum=0,sqr=0;
				query(x,y,1,1);
				sum=sum/(y-x+1);
				printf("%.4lf\n",(sqr/(y-x+1)-sum*sum) );
			}
		}
    }
    //PAUSE;
    return 0;
}