我在写这个线段树题的时候写寄了,通过下数据发现,add之前的方差正常,平均数正常,但add之后的方差就寄了,蒟蒻怀疑是add和pushdown的问题,但是由于太蒻没看出来,请问有没有大佬帮蒟蒻看看qwq
#include <iostream>
#include <iomanip>
using namespace std;
int n;
struct tree {
double a[400001];
double sum[400001];
double square[400001];
double lazy[400001];
void pushup(int k) {
sum[k] = sum[k*2]+sum[k*2+1];
square[k] = square[k*2]+square[k*2+1];
}
void build(int k = 1,int l = 1,int r = n) {
if(l == r) {
sum[k] = a[l];
square[k] = a[l]*a[l];
return ;
}
int mid = (l+r)>>1;
build(k*2,l,mid);
build(k*2+1,mid+1,r);
pushup(k);
}
void pushdown(int k,int l,int r) {
int mid = (l+r)>>1;
int c = lazy[k];
square[k*2] += (mid-l+1)*c*c+2*c*sum[k*2];
square[k*2+1] += (r-mid)*c*c+2*c*sum[k*2+1];
sum[k*2] += lazy[k]*(mid-l+1);
sum[k*2+1] += lazy[k]*(r-mid);
lazy[k*2] += lazy[k];
lazy[k*2+1] += lazy[k];
lazy[k] = 0;
}
double getsum(int x,int y,int k = 1,int l = 1,int r = n) {
if(x <= l && r <= y) {
return sum[k];
}
int mid = (l+r)>>1;
if(lazy[k]) pushdown(k,l,r);
pushup(k);
double ans = 0;
if(x <= mid) ans += getsum(x,y,k*2,l,mid);
if(y > mid) ans += getsum(x,y,k*2+1,mid+1,r);
return ans;
}
double getsquare(int x,int y,int k = 1,int l = 1,int r = n) {
if(x <= l && r <= y) {
return square[k];
}
int mid = (l+r)>>1;
if(lazy[k]) pushdown(k,l,r);
pushup(k);
double ans = 0;
if(x <= mid) ans += getsquare(x,y,k*2,l,mid);
if(y > mid) ans += getsquare(x,y,k*2+1,mid+1,r);
return ans;
}
void add(int x,int y,double c,int k = 1,int l = 1,int r = n) {
if(x <= l && r <= y) {
lazy[k] += c;
square[k] += c*c*(r-l+1)+2*c*sum[k];
sum[k] += (r-l+1)*c;
return;
}
pushdown(k,l,r);
int mid = (l+r)>>1;
if(x <= mid) add(x,y,c,k*2,l,mid);
if(y > mid) add(x,y,c,k*2+1,mid+1,r);
pushup(k);
}
double getaver(int l,int r) {
return getsum(l,r)/((r-l+1)*1.0);
}
double getvar(int l,int r) {
double bom = getaver(l,r);
bom *= bom;
double bim = getsquare(l,r)/((r-l+1)*1.0);
return bim-bom;
}
}tres;
int main() {
int m;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> tres.a[i];
}
tres.build();
while(m--) {
int op;
cin >> op;
if(op == 1) {
int x,y;
double c;
cin >> x >> y >> c;
tres.add(x,y,c);
}
if(op == 2) {
int x,y;
cin >> x >> y;
cout << fixed << setprecision(4) << tres.getaver(x,y) << endl;
}
if(op == 3) {
int x,y;
cin >> x >> y;
cout << fixed << setprecision(4) << tres.getvar(x,y) << endl;
}
}
return 0;
}