本文共 2253 字，大约阅读时间需要 7 分钟。

一、基础操作:区间求和lazy标记

#include 
   
    using namespace std;typedef long long ll;const int maxn=100010;int in[maxn+2];//数据初值 struct tree{	int l,r;	ll lazy,sumn;}a[4*maxn+9];void build(int p,int l,int r){	a[p].l=l,a[p].r=r;	if(l==r){		a[p].sumn=in[l];		return;	}	int mid=(l+r)>>1;	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);	a[p].sumn=a[p<<1].sumn+a[p<<1|1].sumn;}void push_down(int p){//下传懒惰标记 	a[p<<1].sumn+=a[p].lazy*(a[p<<1].r-a[p<<1].l+1);	a[p<<1|1].sumn+=a[p].lazy*(a[p<<1|1].r-a[p<<1|1].l+1);	a[p<<1].lazy+=a[p].lazy;	a[p<<1|1].lazy+=a[p].lazy;	a[p].lazy=0;}void change(int p,int l,int r,int k){	if(l<=a[p].l&&r>=a[p].r){//找到完全覆盖的区间 		a[p].sumn+=k*(a[p].r-a[p].l+1);		a[p].lazy+=k;		return;	}	push_down(p);//下传标记	int mid=a[p].l+a[p].r>>1;	if(l<=mid)	change(p<<1,l,r,k);//和左儿子有交集	if(r>mid)	change(p<<1|1,l,r,k);	a[p].sumn=a[p<<1].sumn+a[p<<1|1].sumn;//维护父子逻辑 }ll ask(int p,int l,int r){//区间询问求和 	if(l<=a[p].l&&r>=a[p].r)	return a[p].sumn;	push_down(p);//每次都要下传标记	int mid=(a[p].l+a[p].r)>>1;	ll ans=0;	if(l<=mid)	ans+=ask(p<<1,l,r);	if(r>mid)	ans+=ask(p<<1|1,l,r);	return ans; }int main(){	std::ios::sync_with_stdio(false);	int n,m,x,b,c,e;	cin>>n>>m;	for(int i=1;i<=n;i++)	cin>>in[i];	build(1,1,n);	for(int i=1;i<=m;i++){		cin>>x;		if(x==1){			cin>>b>>c>>e;			change(1,b,c,e);		}		else{			cin>>b>>c;			cout<
    
     <
    
   

二、区间最大值

#include 
   
    using namespace std;const int maxn=200009;int n,m,in[maxn];struct node{	int v,l,r,lazy;}a[maxn*4];void build(int p,int l,int r){	a[p].l=l,a[p].r=r;	if(l==r){		a[p].v=in[l];		return;	}	int mid=l+r>>1;	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);	a[p].v=max(a[p<<1].v,a[p<<1|1].v);}void change(int p,int l,int r,int k){	if(a[p].l==l&&a[p].r==r){//到达叶子节点 		if(a[p].v
    
     >1;	if(l<=mid)	change(p<<1,l,r,k);//找节点 	else	change(p<<1|1,l,r,k);	a[p].v=max(a[p<<1].v,a[p<<1|1].v);}int Max=0;void ask(int p,int l,int r){	if(a[p].l>=l&&a[p].r<=r){		Max=max(Max,a[p].v);		return;	}	int ans=0;	int mid=a[p].l+a[p].r>>1;	if(l<=mid)	ask(p<<1,l,r);	if(r>mid)	ask(p<<1|1,l,r);	return;}int main(){	string s;	cin>>n>>m;	for(int i=1;i<=n;i++)	cin>>in[i];	int b,c;	build(1,1,n);	for(int i=1;i<=m;i++)	{		cin>>s;		if(s[0]=='U'){			cin>>b>>c;			change(1,b,b,c);		}		else{			Max=0;			cin>>b>>c;			ask(1,b,c);			cout<
     
      <
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/104625130 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！