题解 - 方差 - 核OJ

1

Cross LV 7 @ 2023-7-13 23:06:45

关于方差有这样一个公式，高中数学会学到（不过提高组的要求是掌握高中数学知识吧）：

如果 $n$ 个数的方差为 $s_1^2$ ，平均数为 $\overline x_1$ ， $m$ 个数的方差为 $s_2^2$ ，平均数为 $\overline x_2$ ，这 $n + m$ 个数的平均数为 $\overline x$ ，设方差为 $s^2$ ，则有如下公式：

$s^2 = \frac{n}{n+m} \times [s_1^2 + (\overline x_1 - \overline x_2)^2] + \frac{m}{n+m} \times [s_2^2 + (\overline x_2 - \overline x_2)^2]$

这个公式可以由最基本的公式（题目给的）推出，有了这个公式，就可以由方差推方差了，好处在于不用维护平方和，而且方差表示数据波动程度，意味着给区间加，则这段区间的方差不变！但是坏处，查询函数比较难写。

所以我们要在线段树上维护两个信息：区间和和方差，因为平均数可以由区间和得出所以不用维护，当然也可以维护个平均数可能能更方便。区间合并方差可以用上述公式这样写：

tr[rt][2] = ((mid-l+1) * (tr[rt<<1][2] + (tr[rt][1] - tr[rt<<1][1]) * (tr[rt][1] - tr[rt<<1][1])) + (r-mid) * (tr[rt<<1|1][2] + (tr[rt][1] - tr[rt<<1|1][1]) * (tr[rt][1] - tr[rt<<1|1][1]))) * 1.0 / (r-l+1);

下面就说一下写查询是要注意的地方：我们知道，线段树查询原理是吧一个大区间拆成许多小区间，此题这种写法难在确定子区间长度，既不是简单的当前子区间长度，也不是整个问题的长度。如果当前子区间要一分为二，设当前子区间左边界为 $l$ ，右边界为 $r$ ，整个问题左边界为 $L$ ，右边界为 $R$ ，则当前区间长度为 $\min(R,r) - \max(l,L) + 1$ 。 $mid$ 还是按 $\frac{l+r}{2}$ 取，但左右端点分别为 $\max(l,L),\min(R,r)$ 。当然，要是当前区间中只找左边或只找右边就直接返回即可。

code:

#include <bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int MAXN = 1e5 + 5;
double tr[MAXN<<2][3], add[MAXN<<2], a[MAXN];
//0sum 1avg 2fangcha
void push_up(int l, int r, int rt)
{
	int mid = (l + r) / 2;
	tr[rt][0] = tr[rt<<1][0] + tr[rt<<1|1][0];
	tr[rt][1] = tr[rt][0] / (r-l+1);
	tr[rt][2] = ((mid-l+1) * (tr[rt<<1][2] + (tr[rt][1] - tr[rt<<1][1]) * (tr[rt][1] - tr[rt<<1][1])) + (r-mid) * (tr[rt<<1|1][2] + (tr[rt][1] - tr[rt<<1|1][1]) * (tr[rt][1] - tr[rt<<1|1][1]))) * 1.0 / (r-l+1);
}
void push_down(int l, int r, int rt)
{
	if (!add[rt]) return;
	int mid = (l + r) / 2;
	tr[rt<<1][0] += add[rt] * (mid-l+1); 
	tr[rt<<1|1][0] += add[rt] * (r-mid);
	tr[rt<<1][1] += add[rt];
	tr[rt<<1|1][1] += add[rt];
	add[rt<<1] += add[rt]; add[rt<<1|1] += add[rt];
	add[rt] = 0;
}
void build(int l, int r, int rt)
{
	if (l == r) 
	{
		tr[rt][0] = tr[rt][1] = a[l]; tr[rt][2] = 0;
	}
	else
	{
		int mid = (l + r) / 2;
		build(lson); build(rson);
		push_up(l, r, rt);
	}
}
void update(int L, int R, double x, int l, int r, int rt)
{
	if (L <= l && r <= R)
	{
		tr[rt][0] += (r-l+1) * x;
		tr[rt][1] += x;
		add[rt] += x;
		return;
	}
	int mid = (l + r) / 2;
	push_down(l, r, rt);
	if (mid >= L) update(L, R, x, lson);
	if (mid < R) update(L, R, x, rson);
	push_up(l, r, rt);
}
double query(int L, int R, int l, int r, int rt, int t)
{
	if (L <= l && r <= R)
	{
		if (t == 1) return tr[rt][0];
		if (t == 2) return tr[rt][1];
		if (t == 3) return tr[rt][2];
	}
	int mid = (l + r) / 2;
	push_down(l, r, rt);
	double sum = 0;
	if (mid >= L) sum += query(L, R, lson, 1);
	if (mid < R) sum += query(L, R, rson, 1);
	if (t == 1)
	{
		return sum;
	}
	if (t == 2)
	{
		L = max(L, l); R = min(R, r);
		return sum / (R-L + 1);
	}
	if (t == 3)
	{
		double s1 = -11451412, s2 = -1145141, x1 = 0, x2 = 0, x = sum / (min(R, r)-max(L, l)+1);
		bool f1 = 0, f2 = 0;
		if (mid >= L) s1 = query(L, R, lson, 3), x1 = query(L, R, lson, 2), f1 = 1;
		if (mid < R) s2 = query(L, R, rson, 3), x2 = query(L, R, rson, 2), f2 = 1;
		if (f1 && f2)
		{
			L = max(L, l); R = min(R, r);
			return ((mid-L+1) * (s1 + (x1 - x) * (x1 - x)) + (R-mid) * (s2 + (x2 - x) * (x2-x))) * 1.0 / (R-L+1);
		 } 
		else if (f1)
		{
			return s1;
		}
		else if (f2)
		{
			return s2;
		}
	}
}
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	build(1, n, 1);//cout << tr[1][0] << endl;
	for (int i = 1; i <= m; i++)
	{
		int op, x, y;
		double k;
		cin >> op >> x >> y;
		if (op == 1)
		{
			cin >> k;
			update(x, y, k, 1, n, 1);
		}
		else
		{
			printf("%.4lf\n",query(x, y, 1, n, 1, op));
		}
	}
	
	return 0;
}

1

poaspoas LV 7 MOD @ 2023-6-25 10:54:34

#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define mid (l+r>>1)
using namespace std;
const int N=100005;
int n,m,k,s,t;
double a[N],ans,ans2;
struct node{
	double sum[N<<2],tag[N<<2],sum2[N<<2];
	// sum:和 tag：标记 sum2：平方和 
	void update(int p){
		sum[p]=sum[p<<1]+sum[p<<1|1];
		sum2[p]=sum2[p<<1]+sum2[p<<1|1];
	}
	void down(int p,int l,int r,double k){
	// 区间[l,r]整体增加k 
		sum2[p]+=2*k*sum[p]+(r-l+1)*k*k;
		sum[p]+=(r-l+1)*k;
		//注意要先更新sum2，也就是区间的平方的和，再更新sum，也就是区间和 
		tag[p]+=k;
	} 
	void build(int p,int l,int r){
		if (l==r) {
			sum[p]=a[l];
			sum2[p]=a[l]*a[l];
			return;
		}
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		update(p);
	}
	void change(int p,int l,int r,int s,int t,double k){
	//[s,t] 增加k
		if (l>=s && r<=t){
			down(p,l,r,k);
			return;
		} 
		if (tag){
			down(p<<1,l,mid,tag[p]);
			down(p<<1|1,mid+1,r,tag[p]);
			tag[p]=0;
		}
		if (s<=mid) change(p<<1,l,mid,s,t,k);
		if (t>mid) change(p<<1|1,mid+1,r,s,t,k);
		update(p);
	}
	void query(int p,int l,int r,int s,int t){
	//查询[s,t]的和 以及平方和 
		if (l>=s && r<=t){
			ans+=sum[p];
			ans2+=sum2[p];
			return;
		}
		if (tag){
			down(p<<1,l,mid,tag[p]);
			down(p<<1|1,mid+1,r,tag[p]);
			tag[p]=0;
		}
		if (s<=mid) query(p<<1,l,mid,s,t);
		if (t>mid) query(p<<1|1,mid+1,r,s,t);
	} 
}T;
int main(){ 
	freopen("in.txt","r",stdin);
	cin>>n>>m;
	for (int i=1;i<=n;++i) cin>>a[i];
	T.build(1,1,n);
	int opt,l,r;double x;
	for (int i=1;i<=m;++i){
		cin>>opt>>l>>r;
		if (opt==1){
			cin>>x;
			T.change(1,1,n,l,r,x);
		}
		if (opt==2){
			ans=ans2=0;
			T.query(1,1,n,l,r);
			printf("%.4f\n",ans/(r-l+1));
		}
		if (opt==3){
			ans=ans2=0;
			T.query(1,1,n,l,r);
			ans/=(r-l+1);
			ans2/=(r-l+1);
			printf("%.4f\n",-ans*ans+ans2);
		}
	} 
}

0

wsy1998 @ 2023-7-5 1:31:24

不考虑操作 $3$ 的时候，就是线段树模板(一)。

再有了操作 $3$ ,需要求方差的时候，需要推式子，详细过程在上面题解已经展示，然后维护一下区间和，以及区间平方和即可。

注意该定义double的不要写错。

#include <bits/stdc++.h>
#define ll long long
#define ls p << 1
#define rs p << 1 | 1
using namespace std;
const int N = 1e5 + 5;
int n, m;
double a[N];
struct segment_tree
{
    int l, r;
    double sum, res, tag;//和，平方和，懒标记
} t[N << 2];
void push_up(int p)
{
    t[p].sum = t[ls].sum + t[rs].sum;
    t[p].res = t[ls].res + t[rs].res;
}
void build(int p, int l, int r)
{
    t[p].l = l, t[p].r = r;
    if (l == r)
    {
        t[p].sum = a[l];
        t[p].res = a[l] * a[l];
        return ;
    }
    int mid = l + r >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    push_up(p);
}
void push_down(int p)
{
    int mid = t[p].l + t[p].r >> 1;
    if (t[p].tag)
    {
        t[ls].res += (mid - t[ls].l + 1) * t[p].tag * t[p].tag + 2 * t[p].tag * t[ls].sum;
        t[rs].res += (t[rs].r - mid) * t[p].tag * t[p].tag + 2 * t[p].tag * t[rs].sum;
        t[ls].sum += (mid - t[ls].l + 1) * t[p].tag;
        t[rs].sum += (t[rs].r - mid) * t[p].tag;
        t[ls].tag += t[p].tag;
        t[rs].tag += t[p].tag;
        t[p].tag = 0;
    }
}
void change(int p, int l, int r, double k)
{
    if (l <= t[p].l && r >= t[p].r)
    {
        t[p].tag += k;
        t[p].res += (t[p].r - t[p].l + 1) * k * k + 2 * k * t[p].sum;
        t[p].sum += (t[p].r - t[p].l + 1) * k;
        return ;
    }
    push_down(p);
    int mid = t[p].l + t[p].r >> 1;
    if (l <= mid) change(ls, l, r, k);
    if (r > mid) change(rs, l, r, k);
    push_up(p);
}
double query1(int p, int l, int r)
{
    if (l <= t[p].l && r >= t[p].r)
    {
        return t[p].sum;
    }
    double ans = 0;
    push_down(p);
    int mid = t[p].l + t[p].r >> 1;
    if (l <= mid) ans += query1(ls, l, r);
    if (r > mid) ans += query1(rs, l, r);
    return ans;
}
double query2(int p, int l, int r)
{
    if (l <= t[p].l && r >= t[p].r)
    {
        return t[p].res;
    }
    double ans = 0;
    push_down(p);
    int mid = t[p].l + t[p].r >> 1;
    if (l <= mid) ans += query2(ls, l, r);
    if (r > mid) ans += query2(rs, l, r);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (m--)
    {
        int op, x, y;
        double k;
        cin >> op >> x >> y;
        if (op == 1)
        {
            cin >> k;
            change(1, x, y, k);
        }
        else if (op == 2)
        {
            double ans = query1(1, x, y);
            cout << fixed << setprecision(4) << ans / (y - x + 1) << "\n";
        }
        else
        {
            double ans1 = query1(1, x, y);
            double avg1 = ans1 / (y - x + 1);
            double ans2 = query2(1, x, y);
            double avg2 = ans2 / (y - x + 1);
            cout << fixed << setprecision(4) << -avg1 * avg1 + avg2 << "\n";
        }
    }
    return 0;
}

0

hetao2863173 LV 10 @ 2023-6-23 8:41:23

部分代码

struct node
{
	double lazy,sum;
} t1[N<<2],t2[N<<2];
double a[N];
inline void Push_up(int rt)
{
	t1[rt].sum=t1[rt<<1].sum+t1[rt<<1 | 1].sum;
	t2[rt].sum=t2[rt<<1].sum+t2[rt<<1 | 1].sum;
}
void build(int rt,int l,int r)
{
	if (l==r)
	{
		t1[rt].sum=a[l];
		t2[rt].sum=a[l]*a[l];
		return;
	}
	build(Lson);
	build(Rson);
	Push_up(rt);
}
inline void Push_down(int rt,int l,int r)
{
	if (!(t1[rt].lazy || t2[rt].lazy))
		return ;
	t2[rt<<1].lazy+=t2[rt].lazy;
	t2[rt<<1].sum+=t1[rt<<1].sum*(t2[rt].lazy*2)+(mid-l+1)*(t2[rt].lazy*t2[rt].lazy);
	t2[rt<<1 | 1].lazy+=t2[rt].lazy;
	t2[rt<<1 | 1].sum+=t1[rt<<1 | 1].sum*(t2[rt].lazy*2)+(r-mid)*(t2[rt].lazy*t2[rt].lazy);
	t2[rt].lazy=0;
	t1[rt<<1].lazy+=t1[rt].lazy;
	t1[rt<<1].sum+=(mid-l+1)*t1[rt].lazy;
	t1[rt<<1 | 1].lazy+=t1[rt].lazy;
	t1[rt<<1 | 1].sum+=(r-mid)*t1[rt].lazy;
	t1[rt].lazy=0;
}
double Query(int rt,int l,int r,int L,int R,int x)
{
	if (L<=l && r<=R)
		return x==1 ? t1[rt].sum:t2[rt].sum;
	double ans=0;
	Push_down(rt,l,r);
	if (L<=mid)
		ans+=Query(Lson,L,R,x);
	if (R>mid)
		ans+=Query(Rson,L,R,x);
	return ans;
}
void Update(int rt,int l,int r,int L,int R,double v)
{
	if (L<=l && r<=R)
	{
		t2[rt].lazy+=v;
		t2[rt].sum+=t1[rt].sum*(v*2)+len*(v*v);
		t1[rt].lazy+=v;
		t1[rt].sum+=len*v;
		return ;
	}
	Push_down(rt,l,r);
	if (L<=mid)
		Update(Lson,L,R,v);
	if (R>mid)
		Update(Rson,L,R,v);
	Push_up(rt);
}
inline void init()
{
//	freopen("data.in","r",stdin);
//	freopen("a.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)
		scanf("%lf",&a[i]);
	build(1,1,n);
	while(m--)
	{
		int x,a,b;
		scanf("%d%d%d",&x,&a,&b);
		if (x==1)
		{
			double c;
			scanf("%lf",&c);
			Update(1,1,n,a,b,c);
		}
		if (x==2)
			printf("%.4lf\n",Query(1,1,n,a,b,1)/((b-a+1)*1.0));
		if (x==3)
		{
			double cnt=(b-a+1)*1.0;
			double ans=Query(1,1,n,a,b,2)/cnt,x_ba=Query(1,1,n,a,b,1)/cnt;
			double ans2=x_ba*x_ba;
			ans-=ans2;
			printf("%.4lf\n",ans);
		}
	}
}

4 条题解

code:

方差

信息

状态

开发

支持

4 条题解

code:

方差

信息

状态

开发

支持

还没有账户？

登录