题解 P1471 【方差】

这道题是一道有一定大力推式子思考难度的裸线段树题

首先我们将求方差的式子展开($S^2$代表方差，$x_i$代表数列的第i项，$n$代表项数，$\bar{x}$代表数列的平均值)：

$S^2=\frac{1}{n}\sum_{i=1}^n(x_i-\bar{x})^2$

将每个平方展开，得：

$S^2=\frac{{\sum_{i=1}^n(x^2)}-{2*\sum_{i=1}^n(x_i*\bar{x})}+n*\bar{x}^2}{n}$

$S^2=\frac{\sum_{i=1}^n({x_i}^{2})}{n}-\bar{x}^2$

好了，展开完成！

观察算式，我们发现我们只需要维护$\sum_{i=1}^n{x_i}^{2}$和$\sum_{i=1}^nx_i$即可。在查询时我们通过线段树算出$\sum_{i=1}^n{x_i}^{2}$和$\sum_{i=1}^nx_i$，并套方差公式就行了（平均值同理）。

还有一个问题：在打tag的时候，如何快速更新$\sum_{i=1}^n{x_i}^{2}$?

大力推算式（假设增加的数是$x$）：

$\sum_{i=1}^n{(a_i+x)}^2$

$=\sum_{i=1}^n{a_i}^2+2*a_i*x+x^2*n$

减去$\sum_{i=1}^n{x_i}^{2}$后：

$2*(\sum_{i=1}^na_i*x)+x^2*n$

问题解决！

这下就能愉快地用线段树维护了_{注意要用double存储}

喜闻乐见的放代码时间：

#include<iostream>
#include<cstdio>
using namespace std;
#define db double
#define ls (root<<1)
#define rs ((root<<1)+1)
#define mid ((l+r)>>1)//蒟蒻喜欢用宏定义
struct node{
	db sum;
	db pfsum;//平方和
	db tag;
} a[400005];
db data[100005];
inline void pushup(int root){
	a[root].sum=a[ls].sum+a[rs].sum;
	a[root].pfsum=a[ls].pfsum+a[rs].pfsum;
}
void build(int root,int l,int r){
	a[root].tag=0;
	if(l==r){
		a[root].sum=data[l];
		a[root].pfsum=data[l]*data[l];
		return;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(root);
}//没什么好说的
inline void pd(int root,int l,int r){
	if(a[root].tag==0)return;
	a[ls].tag+=a[root].tag;
	a[rs].tag+=a[root].tag;
	a[ls].pfsum+=(2*a[ls].sum*a[root].tag+a[root].tag*a[root].tag*(mid-l+1));
	a[rs].pfsum+=(2*a[rs].sum*a[root].tag+a[root].tag*a[root].tag*(r-mid));
	a[ls].sum+=a[root].tag*(mid-l+1);
	a[rs].sum+=a[root].tag*(r-mid);
	a[root].tag=0;
}//push_down 套公式即可
void add(int root,int l,int r,int ql,int qr,db x){
	if(ql<=l&&qr>=r){
		a[root].tag+=x;
		a[root].pfsum+=(2*a[root].sum*x+x*x*(r-l+1));//这里也是套公式
		a[root].sum+=(r-l+1)*x;
		return;
	}
	if(ql>r||qr<l)
		return;
	pd(root,l,r);
	if(ql<=mid)
		add(ls,l,mid,ql,qr,x);
	if(qr>mid)
		add(rs,mid+1,r,ql,qr,x);
	pushup(root);
	return;
}
db qsum(int root,int l,int r,int ql,int qr){
	if(ql<=l&&qr>=r){
		return a[root].sum;
	}
	if(ql>r||qr<l)
		return 0.0;
	pd(root,l,r);
	db ret=0;
	if(ql<=mid)
		ret+=qsum(ls,l,mid,ql,qr);
	if(qr>mid)
		ret+=qsum(rs,mid+1,r,ql,qr);
	return ret;
}
db qpfsum(int root,int l,int r,int ql,int qr){
	if(ql<=l&&qr>=r){
		return a[root].pfsum;
	}
	if(ql>r||qr<l)
		return 0.0;
	pd(root,l,r);
	db ret=0;
	if(ql<=mid)
		ret+=qpfsum(ls,l,mid,ql,qr);
	if(qr>mid)
		ret+=qpfsum(rs,mid+1,r,ql,qr);
	return ret;
}
int main()
{
	ios::sync_with_stdio(false);
	int n,m,x,y,z;
	db t;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>data[i];
	build(1,1,n);
	for(int i=0;i<m;i++){
		cin>>x>>y>>z;
		if(x==1){
			cin>>t;
			add(1,1,n,y,z,t);
		}
		else if(x==2)
			printf("%.4lf\n",qsum(1,1,n,y,z)*1.0/(z-y+1.0));//套公式，注意输出格式
		else if(x==3){
			db pj=qsum(1,1,n,y,z)*1.0/(z-y+1.0);
			printf("%.4lf\n",(qpfsum(1,1,n,y,z)*1.0)/(z-y+1.0)-pj*pj);//还是套公式	
		}
	}
	return 0;
}//完结撒花！