跳到主要内容

方差

· 阅读需 4 分钟

题意：区间修改值，区间查询和

解题思路：构史数学题是这样的

对于l到r的平均数，xˉ=∑i=lra[i]r−l+1对于l到r的方差，s2=∑i=lr(a[i]−xˉ)2r−l+1=∑i=lra[i]2−2xˉ∑i=lra[i]r−l+1+xˉ=∑i=lr(a[i])2r−l+1−xˉ2\begin{aligned} &对于l到r的平均数，\bar x=\frac{\sum_{i=l}^{r}a[i]}{r-l+1} \\ &对于l到r的方差，s^2=\frac{\sum_{i=l}^{r}{(a[i]-\bar x)}^2}{r-l+1}=\frac{\sum_{i=l}^{r}{a[i]}^2-2\bar x\sum_{i=l}^{r}a[i]}{r-l+1}+\bar x=\frac{\sum_{i=l}^{r}{(a[i])}^2}{r-l+1}-{\bar x}^2\\ \end{aligned}

所以我们考虑利用线段树维护区间和&区间平方和，推导一下公式得到

对于l到r的和，∑i=lr(a[i]+add)=∑i=lra[i]+add×(r−l+1)对于l到r的平方和，∑i=lr(a[i]+add)2=∑i=lr(a[i])2+2×add∑i=lra[i]+add2×(r−l+1)\begin{aligned} &对于l到r的和，\sum_{i=l}^{r}(a[i]+add)=\sum_{i=l}^{r}a[i]+add\times ( r-l+1 ) \\ &对于l到r的平方和，\sum_{i=l}^{r}(a[i]+add)^2=\sum_{i=l}^{r}(a[i])^2+2\times add\sum_{i=l}^{r}a[i]+add^2\times (r-l+1) \\ \end{aligned}

在线维护并输出切掉本题，在维护线段树的值时需要注意先更新平方和，因为它的计算会使用当前区间的区间和

AC代码
Details
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;

struct Segment_tree
{
    double sum, sqa, add;
    int l, r;
}st[4*N];

double a[N];

void build( int p,int l,int r )
{
    st[p].l=l, st[p].r=r, st[p].add=0;
    if( l == r )
    {
        st[p].sum=a[l], st[p].sqa=a[l]*a[l];
        return ;
    }
    int mid=( l+r )>>1;
    build( p*2,l,mid );
    build( p*2+1,mid+1,r );
    st[p].sum=st[p*2].sum+st[p*2+1].sum;
    st[p].sqa=st[p*2].sqa+st[p*2+1].sqa;
}

void updata( int p )
{
    st[p*2].add+=st[p].add;
	st[p*2+1].add+=st[p].add;
	st[p*2].sqa+=2*st[p].add*st[p*2].sum+( st[p*2].r-st[p*2].l+1 )*st[p].add*st[p].add;
    st[p*2+1].sqa+=2*st[p].add*st[p*2+1].sum+( st[p*2+1].r-st[p*2+1].l+1 )*st[p].add*st[p].add;
    st[p*2].sum+=( st[p].add*( st[p*2].r-st[p*2].l+1 ) );
	st[p*2+1].sum+=( st[p].add*( st[p*2+1].r-st[p*2+1].l+1 ) );
    st[p].add=0;
}

void add( int p,int l,int r,double k )
{
    if( st[p].l >= l && st[p].r <= r )
    {
        st[p].sqa+=2*k*st[p].sum+k*k*( st[p].r-st[p].l+1 ), st[p].sum+=k*( st[p].r-st[p].l+1 ), st[p].add+=k;
        return ;
    }
    updata( p );
    int mid=( st[p].l+st[p].r )>>1;
    if( mid >= l ) add( p*2,l,r,k );
    if( mid < r )  add( p*2+1,l,r,k );
    st[p].sum=st[p*2].sum+st[p*2+1].sum;
    st[p].sqa=st[p*2].sqa+st[p*2+1].sqa;
}

double query_sum( int p,int l,int r )
{
    if( st[p].l >= l && st[p].r <= r )
    {
        return st[p].sum;
    }
    updata( p );
    int mid=( st[p].l+st[p].r )>>1;
    double ans=0;
    if( mid >= l ) ans+=query_sum( p*2,l,r );
    if( mid < r )  ans+=query_sum( p*2+1,l,r );
    return ans;
}

double query_sqa( int p,int l,int r )
{
    if( st[p].l >= l && st[p].r <= r )
    {
        return st[p].sqa;
    }
    updata( p );
    int mid=( st[p].l+st[p].r )>>1;
    double ans=0;
    if( mid >= l ) ans+=query_sqa( p*2,l,r );
    if( mid < r )  ans+=query_sqa( p*2+1,l,r );
    return ans;
}

int main()
{
//	freopen( "txt.in","r",stdin );
    ios::sync_with_stdio( false );
    cin.tie( nullptr );
    int n, m;
    cin>>n>>m;
    for( int i=1;i<=n;i++ )
    {
        cin>>a[i];
    }
    build( 1,1,n );
    for( int i=1;i<=m;i++ )
    {
        int op, x, y;
        cin>>op>>x>>y;
        if( op == 1 )
        {
            double k;
            cin>>k;
            add( 1,x,y,k );
        }
        else if( op == 2 )
        {
        	double ans=query_sum( 1,x,y )/( y-x+1 );
            cout<<fixed<<setprecision( 4 )<<ans<<"\n";
        }
        else
        {
        	double ans1=query_sqa( 1,x,y )/( y-x+1 ), ans2=query_sum( 1,x,y )/( y-x+1 );
        	ans1=ans1-ans2*ans2;
            cout<<fixed<<setprecision( 4 )<<ans1<<"\n";
        }
    }
}

时间复杂度：O(nlog(n))O( nlog(n) )