题解 LuoGu P1471 方差

# 题解 LuoGu P1471 方差

– 题目描述
蒟蒻HansBug在一本数学书里面发现了一个神奇的数列，包含N个实数。他想算算这个数列的平均数和方差。

– 输入格式：
第一行包含两个正整数N、M，分别表示数列中实数的个数和操作的个数。

– 第二行包含N个实数，其中第i个实数表示数列的第i项。

– 接下来M行，每行为一条操作，格式为以下两种之一：

– 操作1：1 x y k ，表示将第x到第y项每项加上k，k为一实数。

– 操作2：2 x y ，表示求出第x到第y项这一子数列的平均数。

– 操作3：3 x y ，表示求出第x到第y项这一子数列的方差。

– 输出格式：
输出包含若干行，每行为一个实数，即依次为每一次操作2或操作3所得的结果（所有结果四舍五入保留4位小数）。


## 想法

对于操作2 我们只用求出[x,y]区间的和然后除以该区间元素数量即可，由于平均值是随区间而不定的，所以我们无法利用线段树存储区间平均值，直接计算即可

对于操作3 我们需要算出区间每个元素减去区间平均值后平方，再求和，后除以元素数量

由于(a- \bar A)^{2}=(a^{2}-2 \times a \times \bar A+\bar A^{2})

所以 S^{2}=\frac{1}{n} \times ( \sum _ {i=l}^{r}a_{i}^{2}-2 \times \sum_{i=l}^{r}a_{i} \times \bar A+ (r-l+1) \times \bar A^{2} )
其中 \sum_{i=l}^{r}a_{i} 为区间和，我们已经在求平均值的时候维护了

而 \bar A 我们可以计算得出

“`math
(a- \bar A)^{2}=(a^{2}-2 \times a \times \bar A+\bar A^{2})

S^{2}=\frac{1}{n} \times ( \sum _ {i=l}^{r}a_{i}^{2}-2 \times \sum_{i=l}^{r}a_{i} \times \bar A+ (r-l+1) \times \bar A^{2} )

\sum_{i=l}^{r}a_{i}

\bar A

\sum _{i}=_ {2}a{i}

“`

故我们仅用再维护 \sum_{i=_ {2}a{i} 即可，即再维护一个平方和

而给a加上b，也可以通过该方法添加

代码如下：

“`cpp
#include
#define N 100021
double a[N],sum[N*4],cov[N*4];
double sum2[N*4];
int n,m;
inline void pushdown(int cur,int x){
sum2[cur<<1]+=2*sum[cur<<1]*cov[cur]+cov[cur]*cov[cur]*(x+1>>1);
sum2[cur<<1|1]+=2*sum[cur<<1|1]*cov[cur]+cov[cur]*cov[cur]*(x>>1);
sum[cur<<1|1]+=(x>>1)*cov[cur^];
sum[cur<<1]+=(x+1>>1)*cov[cur];
cov[cur<<1]+=cov[cur]; cov[cur<<1|1]+=cov[cur]; cov[cur]=0; } inline void pushup(int cur,int x){ sum[cur]=sum[cur<<1]+sum[cur<<1|1]; sum2[cur]=sum2[cur<<1]+sum2[cur<<1|1]; } inline void add(int l,int r,int L,int R,double x,int cur){ if(L<=l&&r<=R){ sum2[cur]+=2*sum[cur]*x+x*x*(r-l+1); sum[cur]+=(r-l+1)*x; cov[cur]+=x; return ; } pushdown(cur,r-l+1); int mid=l+r>>1;
if(L<=mid) add(l,mid,L,R,x,cur<<1); if(R>mid) add(mid+1,r,L,R,x,cur<<1|1); pushup(cur,r-l+1); } inline double ask(int l,int r,int L,int R,int cur,int od){ if(L<=l&&r<=R&&od==1){ return sum[cur]; } if(L<=l&&r<=R&&od==2){ return sum2[cur]; } pushdown(cur,r-l+1); int mid=l+r>>1;double ans=0;
if(L<=mid) ans+=ask(l,mid,L,R,cur<<1,od); if(mid>1;
build(l,mid,cur<<1); build(mid+1,r,cur<<1|1); pushup(cur,r-l+1); } int main (){ scanf("%d %d ",&n,&m); for(int i=1;i<=n;++i) scanf("%lf",&a[i]); build(1,n,1); for(int i=1;i<=m;++i){ int od,x,y;double z; scanf("%d",&od); if(od==1){ scanf("%d %d %lf",&x,&y,&z); add(1,n,x,y,z,1); } if(od==2){ scanf("%d %d",&x,&y); z=(1.0*ask(1,n,x,y,1,1))/(1.0*(y-x+1)); printf("%.4lf\n",z); } if(od==3){ scanf("%d %d",&x,&y); z=askvar(1,n,x,y,1)*1.0; z=(z*1.0)/(y-x+1); printf("%.4lf\n",z); } } return 0; } ```