区间加 区间求和
最近学了下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; }