P1471 方差 线段树维护区间方差

P1471 方差 线段树维护区间方差

题意

线段树练习题，给定(n)个实数，(m)个询问，三种操作：

区间加(k)

区间均值

区间方差

[1 leq n leq 1e5\ 1 leq m leq 1e5\ ]

分析

显然区间均值是好维护的，只要求区间和就可以了。

区间均值直接看好像不好维护：于是拆开来看看

[S^2 = frac{1}{n} sum(overline x - x_i)^2\ = frac{1}{n} sum (x_i^2 - 2x_ioverline x + overline x^2)\ = frac{1}{n} (sum x_i^2 - 2overline x sum x_i + n overline x^2)\ = frac{sum x_i^2}{n} - overline x^2 ]

于是只需要维护区间平方和即可。

现在看看怎么区间修改

[sum1 = sum x_i\ sum2 = sum x_i^2\ 区间+k => sum (x_i + k)^2 = sum x_i^2 + 2ksum x_i + nk^2 = sum2 + 2ksum1 + nk^2 ]

发现可以通过区间和维护

代码

#include<bits/stdc++.h>
#define eps 1e-8
#define equals(a,b) (fabs(a - b) < eps)
using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

ll rd(){
	ll x = 0;
	int f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == -1) f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	} 
	return  x * f;
}

struct SegmentTree{
	int n;
	vector<double> sum,ssum,tag;
	SegmentTree(int n):n(n),sum(((n + 1) << 2)),ssum(((n + 1) << 2)),tag(((n + 1) << 2)) {}
	int push_up(int i){
		sum[i] = sum[i << 1] + sum[i << 1|1];
		ssum[i] = ssum[i << 1] + ssum[i << 1|1];
	}
	void update(int i,int l,int r,double v){
		ssum[i] += 2 * v * sum[i] + (r - l + 1) * v * v;   
		sum[i] += (r - l + 1) * v;
		tag[i] += v;
	}
	void push(int i,int l,int r){
		int mid = l + r >> 1;
		if(!equals(tag[i],0)) {
			update(i << 1,l,mid,tag[i]);
			update(i << 1|1,mid + 1,r,tag[i]);
			tag[i] = 0;
		}
	}
	void update(int i,int l,int r,int L,int R,double v){
		if(l > R || r < L) return;
		if(l >= L && r <= R) return update(i,l,r,v);
		int mid = l + r >> 1;
		push(i,l,r);
		update(i << 1,l,mid,L,R,v);
		update(i << 1|1,mid + 1,r,L,R,v);
		push_up(i);
	} 
	double query1(int i,int l,int r,int L,int R){
		if(l > R || r < L) return 0;
		if(l >= L && r <= R) return sum[i];
		int mid = l + r >> 1;
		push(i,l,r);
		return query1(i << 1,l,mid,L,R) + query1(i << 1|1,mid + 1,r,L,R); 
	}
	double query2(int i,int l,int r,int L,int R){
		if(l > R || r < L) return 0;
		if(l >= L && r <= R) return ssum[i];
		int mid = l + r >> 1;
		push(i,l,r);
		return query2(i << 1,l,mid,L,R) + query2(i << 1|1,mid + 1,r,L,R); 
	} 
};

int main(){
	int n = rd();
	int m = rd();
	SegmentTree seg(n);
	for(int i = 1;i <= n;i++){
		double x;
		scanf("%lf",&x);
		seg.update(1,1,n,i,i,x);
	}
	while(m--){
		int op = rd();
		if(op == 1) {
			int x = rd();
			int y = rd();
			double v;
			scanf("%lf",&v);
			seg.update(1,1,n,x,y,v); 
		}
		else if(op == 2) {
			int x = rd();
			int y = rd();
			printf("%.4f
",seg.query1(1,1,n,x,y) / (y - x + 1));
		}
		else {
			int x = rd();
			int y = rd();
			double res = seg.query2(1,1,n,x,y);
			double tmp = seg.query1(1,1,n,x,y);
			res /= (y - x + 1);
			tmp /= (y - x + 1);
			res = res - tmp * tmp;
			printf("%.4f
",res);
		}
	}
}