线段树模版

求和模版

https://www.luogu.com.cn/problem/P3372

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int maxn = 1e5+5;
int n,m;
struct linetree{
	int l,r,data;
}t[4*maxn];
int a[maxn],tag[maxn*4];
int lc(int x){
	return x<<1;
}
int rc(int x){
	return x<<1|1;
}
void push_up(int x){
	t[x].data=t[lc(x)].data+t[rc(x)].data;
	return ;
}
void build(int i,int l,int r){//建树 
	t[i].l=l,t[i].r=r;
	tag[i]=0;
	if(l==r){
		t[i].data=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(lc(i),l,mid);
	build(rc(i),mid+1,r);
	push_up(i);
	return ;
}
void push_down(int i){
	//向下更新 
	//if(!tag[i])return ;
	int mid = (t[i].l+t[i].r)>>1;
	tag[lc(i)]+=tag[i];
	tag[rc(i)]+=tag[i];
	t[lc(i)].data+=(mid-t[i].l+1)*tag[i];
	t[rc(i)].data+=(t[i].r-mid)*tag[i];
	tag[i]=0;
	return ;
}
void updata(int k,int i,int l,int r){
	//目标区间[l,r],当前区间[t[i].l,t[i].r]
	int x=t[i].l,y=t[i].r;//当前区间记录为[x,y]
	if(x>=l&&y<=r){
		t[i].data+=(y-x+1)*k;
		tag[i]+=k;
		return ;
	} 
	push_down(i);
	int mid = (x+y)>>1;
	if(l<=mid)updata(k,lc(i),l,r);
	if(r>mid)updata(k,rc(i),l,r);
	push_up(i);
}
int query(int l,int r,int i){//查询，目标区间 [l,r]
	if(l<=t[i].l&&t[i].r<=r)return t[i].data;
	int ans=0,mid=(t[i].l+t[i].r)>>1;
	push_down(i);
	if(l<=mid)ans+=query(l,r,lc(i));
	if(mid<r)ans+=query(l,r,rc(i));
	return ans;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	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 tmp,x,y,k;
		cin>>tmp;
		if(tmp==1){
			cin>>x>>y>>k;
			updata(k,1,x,y);
		}else{
			cin>>x>>y;
			cout<<query(x,y,1)<<"\n";
			
		}
	}
	return 0;
} 

最大、小模版（无更新）

https://www.luogu.com.cn/problem/P2880

#include <bits/stdc++.h>
using namespace std;
//#define int unsigned long long
const int maxn = 1e5+5;
int n,m;
struct linetree{
	int l,r,data;
	int minn=INT_MAX,maxn=INT_MIN; 
}t[4*maxn];
int a[maxn],tag[maxn*4];
int lc(int x){
	return x<<1;
}
int rc(int x){
	return x<<1|1;
}
void push_up(int x){
	t[x].data=t[lc(x)].data+t[rc(x)].data;
	t[x].maxn=max(t[lc(x)].maxn,t[rc(x)].maxn);
	t[x].minn=min(t[lc(x)].minn,t[rc(x)].minn);
	return ;
}
void build(int i,int l,int r){//建树 
	t[i].l=l,t[i].r=r;
	tag[i]=0;
	if(l==r){
		t[i].data=t[i].maxn=t[i].minn=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(lc(i),l,mid);
	build(rc(i),mid+1,r);
	push_up(i);
	return ;
}
int query_min(int l,int r,int i){//查询，目标区间 [l,r]
	if(l<=t[i].l&&t[i].r<=r)return t[i].minn;
	int ans=INT_MAX,mid=(t[i].l+t[i].r)>>1;
	//push_down(i);
	if(l<=mid)ans=min(ans,query_min(l,r,lc(i)));
	if(mid<r)ans=min(ans,query_min(l,r,rc(i)));
	return ans;
}
int query_max(int l,int r,int i){//查询，目标区间 [l,r]
	if(l<=t[i].l&&t[i].r<=r)return t[i].maxn;
	int ans=INT_MIN,mid=(t[i].l+t[i].r)>>1;
	//push_down(i);
	if(l<=mid)ans=max(ans,query_max(l,r,lc(i)));
	if(mid<r)ans=max(ans,query_max(l,r,rc(i)));
	return ans;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	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 tmp,x,y,k;
		cin>>x>>y;
		cout<<(query_max(x,y,1)-query_min(x,y,1))<<"\n";
	}
	return 0;
}