线段树模板

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cmath> using namespace std; #define maxn 100010 long long sum[maxn<<2],add[maxn<<2]; void pushup(int rt) {     sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void pushdown(int rt ,int l,int r) {     if (add[rt]) {         add[rt<<1]+=add[rt];         add[rt<<1|1]+=add[rt];         sum[rt<<1]+=add[rt]*((l+r)/2-l+1);         sum[rt<<1|1]+=add[rt]*(r-((l+r)/2+1)+1);         add[rt]=0;     } } void build(int l,int r ,int rt) {     if (l==r) {         scanf("%lld",&sum[rt]);         return ;     }     int m=(l+r)>>1;     build(l,m,rt<<1);     build(m+1,r,rt<<1|1);     pushup(rt); } void updata(int x,int y,int z,int l,int r,int rt) {     if (x<=l && r<=y ) {         add[rt]+=z;         sum[rt]+=z*(r-l+1);         return ;     }     pushdown(rt,l,r);     int m=(l+r)>>1;     if (x<=m) updata(x,y,z,l,m,rt<<1);     if (y>m ) updata(x,y,z,m+1,r,rt<<1|1);     pushup(rt); } long long query(int x,int y,int l,int r, int rt) {     long long ans=0;     if (x<=l && r<=y) return sum[rt];     pushdown(rt,l,r);     int m=(l+r)>>1;     if (x<=m) ans+=query(x,y,l,m,rt<<1);     if (y>m ) ans+=query(x,y,m+1,r,rt<<1|1);     return ans; } int main() {     int n,q,t;     scanf("%d",&t);     while(t--) {         scanf("%d",&n);         memset(add,0,sizeof(add));         build(1,n,1);         scanf("%d",&q);         int x,y,z,a;         while(q--) {             scanf("%d",&a);             if (a) {                 scanf("%d%d",&x,&y);                 printf("%.2lf\n",((double)query(x,y,1,n,1)/(y-x+1)));             } else {                 scanf("%d%d%d",&x,&y,&z);                 updata(x,y,z,1,n,1);             }         }     }     return 0; } //更新 #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<math.h> using namespace std; #define maxn 100010 long long sum[4*maxn],add[4*maxn],a[maxn]; void pushup(int rt) {     sum[rt]=sum[2*rt]+sum[2*rt+1]; } void pushdown1(int rt,int l,int r) {     if(add[rt])     {         int mid=(l+r)/2;         add[2*rt]+=add[rt];         add[2*rt+1]+=add[rt];         sum[2*rt]+=(mid-l+1)*add[rt];         sum[2*rt+1]+=(r-(mid+1)+1)*add[rt];         add[rt]=0;     } } void pushdown2(int rt,int l,int r) {     if(add[rt])     {         int mid=(l+r)/2;         add[2*rt]=add[rt];         add[2*rt+1]=add[rt];         sum[2*rt]=(mid-l+1)*add[rt];         sum[2*rt+1]=(r-(mid+1)+1)*add[rt];         add[rt]=0;     } } void build(int l,int r,int rt) {     if(l==r);         sum[rt]=a[r];     else     {         int mid=(l+r)/2;         build(1,mid,2*rt);         build(mid+1,r,2*rt+1);         pushup(rt);     } } void updata1(int x,int y,int z,int l,int r,int rt)//区间更新 x到y区间每个数加z {     if(x<=l&&r<=y)     {         add[rt]+=z;         sum[rt]+=z*(r-l+1);     }     else     {         pushdown(rt,l,r);         int mid=(l+r)/2;         if(x<=mid) updata(x,y,z,l,mid,2*rt);         if(y>=mid+1) updata(x,y,z,mid+1,r,2*rt+1);         pushup(rt);     } } void updata2(int x,int y,int z,int l,int r,int rt)//区间更新，x到y区间的每个数替换成z {     if(x<=l&&r<=y)     {         add[rt]=z;         sum[rt]=z*(r-l+1);     }     else     {         pushdown2(rt,l,r);         int mid=(l+r)/2;         if(x<=mid) updata(x,y,z,l,mid,2*rt);         if(y>=mid+1) updata(x,y,z,mid+1,r,2*rt+1);         pushup(rt);     } } void updatanode(int x,int z,int l,int r,int rt)//单点更新 x位置的数加z {     updata(x,x,z,l,r,rt); } long long query(int x,int y,int l,int r,int rt) {     if(x<=l&&r<=y)  return sum[rt];     else     {         long long ans=0;         pushdown(rt);         int mid=(l+r)/2;         if(x<=mid) ans+=query(x,y,z,l,mid,2*rt);         if(y>=mid+1) ans+=query(x,y,z,mid+1,r,2*rt+1);         return ans;     } }

区间加 区间求和

最近学了下lazy标记永久化，于是又重新写了下这题。

lazy标记永久化，顾名思义就是lazy标记不下放即没有了pushdown，但是为了获得儿子节点的值需要把lazy[rt]的值放到query函数的参数里，往儿子节点方向搜索时带下去。另外update函数的话也是有较之前有变化，体现在现在更新rt节点的值不是把左右子树都更新完了后pushup了，这样会出错，因为儿子节点的sum可能还是以为的值，那么一pushup就错了，解决办法就是每次更新到一个点，马上求出交集对rt点的sum更新。差别大概就是这些了。

/* #include<bits/stdc++.h> using namespace std; #define ls rt<<1 #define rs (rt<<1)+1 #define PI acos(-1) #define eps 1e-8 #define ll long long #define fuck(x) cout<<#x<<" "<<x<<endl; typedef pair<int,int> pii; const int inf=2e9; const int maxn=1e6+10; int d[4][2]={1,0,-1,0,0,1,0,-1}; //int lowbit(int x){return x&-x;} //void add(int x,int v){while(x<=n)bit[x]+=v,x+=lowbit(x);} //int sum(int x){int ans=0;while(x>=1) ans+=bit[x],x-=lowbit(x);return ans;} inline ll read() { ll s = 0,w = 1; char ch = getchar(); while(!isdigit(ch)) { if(ch == '-') w = -1; ch = getchar(); } while(isdigit(ch)) s = s * 10 + ch - '0',ch = getchar(); return s * w; } inline void write(ll x) { if(x < 0) putchar('-'), x = -x; if(x > 9) write(x / 10); putchar(x % 10 + '0'); } int gcd(int x,int y){ return y==0?x:gcd(y,x%y); } int n,m,k,a[maxn],b[maxn],f[maxn]; ll dp[100005]; int main(){ n=read(); m=read(); k=read(); for(int i=0;i<=k;i++) f[i]=read(); for(int i=1;i<=m;i++) a[i]=read(),b[i]=read(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { for(int k=a[j];k<=1000+a[j];k++) } } return 0; }*/ #include<bits/stdc++.h> using namespace std; #define ls rt<<1 #define rs (rt<<1)+1 #define PI acos(-1) #define eps 1e-8 #define ll long long #define fuck(x) cout<<#x<<" "<<x<<endl; typedef pair<int,int> pii; const int inf=2e9; const int maxn=1e5+10; int d[4][2]={1,0,-1,0,0,1,0,-1}; //int lowbit(int x){return x&-x;} //void add(int x,int v){while(x<=n)bit[x]+=v,x+=lowbit(x);} //int sum(int x){int ans=0;while(x>=1) ans+=bit[x],x-=lowbit(x);return ans;} inline ll read() { ll s = 0,w = 1; char ch = getchar(); while(!isdigit(ch)) { if(ch == '-') w = -1; ch = getchar(); } while(isdigit(ch)) s = s * 10 + ch - '0',ch = getchar(); return s * w; } inline void write(ll x) { if(x < 0) putchar('-'), x = -x; if(x > 9) write(x / 10); putchar(x % 10 + '0'); } int gcd(int x,int y){ return y==0?x:gcd(y,x%y); } ll a[maxn],sum[maxn<<2],lazy[maxn<<2]; void build(int rt,int L,int R){ lazy[rt]=0; if(L==R) { sum[rt]=a[L]; return ; } int mid=(L+R)>>1; build(ls,L,mid); build(rs,mid+1,R); sum[rt]=sum[ls]+sum[rs]; } void update(int rt,int L,int R,int l,int r,ll v){ sum[rt]+=v*(min(r,R)-max(l,L)+1); if(l<=L&&r>=R){ lazy[rt]+=v; return ; } int mid=(L+R)>>1; if(r<=mid) update(ls,L,mid,l,r,v); else if(l>mid) update(rs,mid+1,R,l,r,v); else{ update(ls,L,mid,l,r,v); update(rs,mid+1,R,l,r,v); } } ll query(int rt,int L,int R,int l,int r,ll tag){ if(l<=L&&r>=R){ return sum[rt]+tag*(R-L+1); } int mid=(L+R)>>1; ll sum=0; if(r<=mid) sum=query(ls,L,mid,l,r,tag+lazy[rt]); else if(l>mid) sum=query(rs,mid+1,R,l,r,tag+lazy[rt]); else{ sum=query(ls,L,mid,l,r,tag+lazy[rt]); sum+=query(rs,mid+1,R,l,r,tag+lazy[rt]); } return sum; } int main(){ int n,m; n=read();m=read(); for(int i=1;i<=n;i++) a[i]=read(); build(1,1,n); while(m--){ int op,x,y,z; op=read(); if(op==1) { x=read();y=read();z=read(); update(1, 1, n,x,y,z); } else{ x=read();y=read(); printf("%lld\n",query(1,1,n,x,y,0)); } } return 0; }