線分樹、分散、数学(Variance,玲瓏杯Round#5 H lonlife 1063)

分散=(Σ(xi−x)^2)/n,1<=i<=nしか知られていなかった.xは平均数
1本の線分木で分散を維持することはできません.
分散=Var[x]=E[x^2]−E[x]^2は,二乗の期待から所望の二乗を減算することが分かった.
したがって、2つのセグメントツリーで区間と平方の区間とをそれぞれ維持します.そして答えを出せばいい.
私たちは知っています.私たちは知っていますが、私はどうして知りませんか.
これからもっと試合をしなければならないので、試合の収穫が大きいような気がします.
コード#コード#

#include
#define ls (now<<1)
#define rs (ls|1)
using namespace std;
typedef long long ll;
const ll maxn=(1<<16)+10;
typedef pair pdd;

ll n,m;
ll a[maxn];

double tree1[maxn<<2];
double tree2[maxn<<2];

void up_data(ll now)
{
    tree1[now]=tree1[ls]+tree1[rs];
    tree2[now]=tree2[ls]+tree2[rs];
}

ll K;

void BUILD(ll l,ll r,ll now)
{
    if(l==r)
    {
        tree1[now]=a[K];
        tree2[now]=a[K]*a[K];
        K++;
        return;
    }
    ll m=(l+r)>>1;
    BUILD(l,m,ls);
    BUILD(m+1,r,rs);
    up_data(now);
}

void A(ll l,ll r,ll now,ll pos,ll val)
{
    if(l==r)
    {
        tree1[now]=val;
        tree2[now]=val*val;
        return;
    }
    ll m=(l+r)>>1;
    if(pos<=m) A(l,m,ls,pos,val);
    else A(m+1,r,rs,pos,val);
    up_data(now);
}

pdd Q(ll l,ll r,ll now,ll ql,ll qr)
{
    if(ql<=l&&r<=qr) return make_pair(tree1[now],tree2[now]);
    ll m=(l+r)>>1;
    pdd ansl=make_pair(0,0);
    pdd ansr=make_pair(0,0);
    if(ql<=m) ansl=Q(l,m,ls,ql,qr);
    if(qr>m) ansr=Q(m+1,r,rs,ql,qr);
    return make_pair(ansl.first+ansr.first,ansl.second+ansr.second);
}

int main()
{
    while(scanf("%lld %lld",&n,&m)==2)
    {
        for(ll i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        K=1;
        BUILD(1,n,1);
        ll x,y;
        while(m--)
        {
            scanf("%lld",&x);
            if(x==1)
            {
                scanf("%lld %lld",&x,&y);
                A(1,n,1,x,y);
            }
            else
            {
                scanf("%lld %lld",&x,&y);
                ll l=y-x+1;
                pdd p=Q(1,n,1,x,y);
                printf("%lld
",ll(floor((p.second/l-(p.first*p.first/l/l))*l*l+0.5)));
            }
        }
    }
    return 0;
}