P5142 区间方差
题面
对于一个长度为 \(n\) 的序列 \(a_1,a_2,a_3\cdots a_n\)，我们定义它的平均数 \(a\) 为:
\[a=\frac{1}{n}\sum_{i=1}^{n}a_i \]并定义它的方差 \(d\) 为:
\[d=\frac{1}{n}\sum_{i=1}^{n}(a_i-a)^2 \]现在给定一个长度为 \(n\) 的序列 \(b_1,b_2\cdots b_n\)。你需要支持两种操作。每种操作的格式为 c x y。
若 \(c=1\)，为修改操作，代表将 \(b_x\) 赋值为 \(y\)。
若 \(c=2\)，为查询操作，代表查询 \(b_x\) 到 \(b_y\) 的方差。
为了避免浮点数误差，请以分数取模形式输出结果（对 1000000007（\(10^9+7\)）取模）。
输入格式
第一行两个整数 \(n,m\)，代表序列 \(b\) 的长度为 \(n\)，有 \(m\) 个操作。
第二行 \(n\) 个整数 \(b_i\)，表示序列 \(b\) 的初始值。
下面有 \(m\) 行整数，每行格式为 c x y，含义如上文所示。保证所有操作合法。
输出格式
对于每个操作 2，输出一行。
数据规模与约定
- 对于 \(50\%\) 的数据，\(n\leq 1000\)，\(m\leq 1000\)。
- 对于 \(100\%\) 的数据，\(1\leq n,m\leq 1\times 10^5\)，\(1\leq b_i\leq 1\times 10^9\)，\(1\leq x\leq n\)。对于操作 1，\(1\leq y\leq 1\times 10^9\)。对于操作2，\(x\leq y\leq n\)。
思路
这道题可以用树状数组维护。
维护两个树状数组，一个求和，一个求平方和。
对于单点修改，直接模拟单点加即可。
对于求方差，可以把式子变一下形。然后除法用逆元代替。逆元可以用快速幂求。
代码
#include
#define int long long
using namespace std;
const int SIZE = 1e5+5;
const int MOD = 1e9+7;
int a[SIZE],n,m;
struct bit{
int t[SIZE];
void update(int p,int v){
while(p<=n){
t[p]+=v;
t[p]%=MOD;
p+=(p&-p);
}
}
int query(int p){
int result=0;
while(p>0){
result+=(t[p]%MOD);
result%=MOD;
p-=(p&-p);
}
return result;
}
} bit1,bit2;
int power(int a,int b){
int res=1;
while(b){
if(b&1){
res=res*a%MOD;
}
a=a*a%MOD;
b=b>>1;
}
return res;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]%=MOD;
bit1.update(i,(a[i]*a[i])%MOD);
bit2.update(i,a[i]);
}
while(m--){
int op,l,r;
cin>>op>>l>>r;
if(op==1){
bit1.update(l,(r*r%MOD-a[l]*a[l]%MOD+MOD)%MOD);
bit2.update(l,(r-a[l]+MOD)%MOD);
a[l]=r;
}
else{
if(l==r){
const char enld = '\n';
cout<<0<