「LuoguP5142」区间方差

题意：给一个长度为 $n$ 的数列，有 $m$ 个操作，操作有以下两种：

1. 1 x y 代表将第 $x$ 个数赋值为 $y$；

2. 2 x y 代表查询从第 $x$ 个数到第 $y$ 个数的方差，分数取模，模数为 $10^9+7$。

很明显是一道维护区间的题，当然选树状数组(当然也可以用线段树，但树状数组更好做)(但是另外一道题必须用线段树：P1471 方差)。

这题难点就在求方差，我们假设有一个长度为 $k$ 的数列 $x _1,x _2,···,x _k$，我们要求它的方差 $p$，那么：

$$p= \frac{(x _1-\overline{x}) ^2 +(x _2-\overline{x}) ^2+···+(x _k-\overline{x}) ^2}{k}$$

我们把它展开，由于 $\overline{x} = \frac{x _1 + x _2 +···+ x _k}{k}$，于是可以得到：

$$p= \frac{x _1 ^2 + x _2 ^2 +···+ x _k ^2}{k} - \overline{x} ^2$$

于是我们开两个树状数组，分别维护平方和和和就可以了，注意取模和 long long，还要记得分数取模要求逆元。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,m,mod=1e9+7;
long long tree1[101010],tree2[101010];
long long lowbit(long long x)
{
	return x&(-x);
}
long long query1(long long x)
{
	long long sum=0;
	for(int i=x;i;i-=lowbit(i))
		sum=(sum+tree1[i])%mod;
	return sum;
}
long long query2(long long x)
{
	long long sum=0;
	for(int i=x;i;i-=lowbit(i))
		sum=(sum+tree2[i])%mod;
	return sum;
}
void update(long long x,long long val)//赋值操作
{
	long long d1=val-(query1(x)-query1(x-1));
	for(int i=x;i<=n;i+=lowbit(i))
		tree1[i]=(tree1[i]+d1)%mod;
	long long d2=val*val-(query2(x)-query2(x-1));
	for(int i=x;i<=n;i+=lowbit(i))
		tree2[i]=(tree2[i]+d2)%mod;
}
long long power(long long a,long long b,long long p)
{
	long long num=1%p;
	for(;b;b>>=1)
	{
		if(b&1)
			num=num*a%p;
		a=a*a%p;
	}
	return num%p;
}
int inv(long long x)
{
	if(x==1)
		return 1;
	else if(x<1)
		return 0;
	return power(x,mod-2,mod);
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		long long p;
		scanf("%lld",&p);
		update(i,p);
	}
	for(int i=1;i<=m;i++)
	{
		long long c,a,b;
		scanf("%lld%lld%lld",&c,&a,&b);
		if(c==1)
			update(a,b);
		else
		{
			if(a==b)
			{
				printf("0\n");
				continue;
			}
			long long q=inv(b-a+1);
			long long r=(query1(b)-query1(a-1)+mod)%mod*q%mod;
			long long ans=((query2(b)-query2(a-1)+mod)%mod*q%mod-r%mod*r%mod+mod)%mod;
			printf("%lld\n",(ans+mod)%mod);
		}
	}
	return 0;
}