数据结构-线段树

常规
1

今天学了线段树，直接上模板代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int n,m,pl[8*N],pr[8*N],a[8*N];
long long sum[8*N],ans,tag[8*N];
void up(int x){
	sum[x]=sum[x*2]+sum[x*2+1];
}
void add(int x,int k){
	sum[x]+=1ll*k*(pr[x]-pl[x]+1);
	tag[x]+=k;
}
void down(int x){
	if(tag[x]){
		add(2*x,tag[x]);
		add(2*x+1,tag[x]);
		tag[x]=0;
	}
}
void build(int x,int l,int r){
	if(l==r){
		sum[x]=a[l];
		return;
	}
	pl[x]=l,pr[x]=r;
	sum[x]=tag[x]=0;
	int mid=(l+r)/2;
	if(l<=mid) build(x*2,l,mid);
	if(mid<r) build(x*2+1,mid+1,r);
	up(x);
}
void unsins(int x,int l,int r,int L,int R,int k){
	if(L>r||R<l) return;
	if(L<=l&&r<=R){
		add(x,k);
		return;
	}
	down(x);
	int mid=(l+r)/2;
	if(l<=mid) unsins(x*2,l,mid,L,R,k);
	if(mid<r) unsins(x*2+1,mid+1,r,L,R,k);
	up(x);
}
void ask(int x,int l,int r,int L,int R){
	if(L>r||R<l) return;
	if(L<=l&&r<=R){
		ans+=sum[x];
		return;
	}
	down(x);
	int mid=(l+r)/2;
	if(l<=mid) ask(x*2,l,mid,L,R);
	if(mid<r) ask(x*2+1,mid+1,r,L,R);
	up(x);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int ty,x,y,k;
		cin>>ty>>x>>y;
		if(ty==1){
			cin>>k;
			unsins(1,1,n,x,y,k);
		}
		else{
			ans=0;
			ask(1,1,n,x,y);
			cout<<ans<<endl;
		}
	}
    return 0;
}
1 个赞