线段树模版
一埋头扎进线段树一上午 感觉很神奇 几个函数就能把它完整的复现下来
这里有几张基础概念的图
对着代码来想 还是很好理解的
最后 是整理了能够处理总和 最大值和最小值的线段树模版
code：
$\LARGE\color{purple}{代码在这里}$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int qr()
{
char ch=getchar();int x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return f*x;
}
#define qr qr()
const int Ratio=0;
const int N=2000005;
const int maxx=INT_MAX;
int n,m;
int a[N];
//线段树
struct stree
{
int l,r;
int dat,sum,miin;
}t[4*N];
void build(int id,int l,int r)//建树
{
t[id].l=l,t[id].r=r;
if(l==r)
{
t[id].dat=a[l];
t[id].sum=a[l];
t[id].miin=a[l];
return;
}
int m=(l+r)>>1;
build(id*2,l,m);
build(id*2+1,m+1,r);
t[id].dat=max(t[id*2].dat,t[id*2+1].dat);
t[id].sum=t[id*2].sum+t[id*2+1].sum;
t[id].miin=min(t[id*2].miin,t[id*2+1].miin);
}
void changesum(int id,int x,int k)//求总和更新值
{
if(t[id].l==t[id].r)
{
t[id].sum+=k;
return;
}
if(x<=t[id*2].r)
changesum(id*2,x,k);
else
changesum(id*2+1,x,k);
t[id].sum=t[id*2].sum+t[id*2+1].sum;
return;
}
void changedat(int id,int x,int k)//求最大更新值
{
if(t[id].l==t[id].r)
{
t[id].dat=k;
return;
}
int m=(t[id].l+t[id].r)>>1;
if(x<=m)
changedat(id*2,x,k);
else
changedat(id*2+1,x,k);
t[id].dat=max(t[id*2].dat,t[id*2+1].dat);
return;
}
void changemin(int id,int x,int k)//求最小更新值
{
if(t[id].l==t[id].r)
{
t[id].miin=k;
return;
}
int m=(t[id].l+t[id].r)>>1;
if(x<=m)
changemin(id*2,x,k);
else
changemin(id*2+1,x,k);
t[id].miin=min(t[id*2].miin,t[id*2+1].miin);
return;
}
int srchsum(int id,int l,int r)//求总和
{
if(l<=t[id].l&&r>=t[id].r)
return t[id].sum;
if(t[id].r<l||t[id].l>r)
return 0;
int s=0;
if(t[id*2].r>=l)
s+=srchsum(id*2,l,r);
if(t[id*2+1].l<=r)
s+=srchsum(id*2+1,l,r);
return s;
}
int srchdat(int id,int l,int r)//求最大值
{
if(l<=t[id].l&&r>=t[id].r)
return t[id].dat;
int v=-maxx;
int mid=(t[id].l+t[id].r)>>1;
if(l<=mid)
v=max(v,srchdat(id*2,l,r));
if(r>mid)
v=max(v,srchdat(id*2+1,l,r));
return v;
}
int srchmin(int id,int l,int r)//求最小值
{
if(l<=t[id].l&&r>=t[id].r)
return t[id].miin;
int v=maxx,mid=(t[id].l+t[id].r)>>1;
if(l<=mid)
v=min(v,srchmin(id*2,l,r));
if(r>mid)
v=min(v,srchmin(id*2+1,l,r));
return v;
}
int main()
{
// 用不上自行删除QwQ
n=qr,m=qr;
for(int i=1;i<=n;i++)
a[i]=qr;
for(int i=1;i<=m;i++)
{
int x=qr,y=qr;
// printf("%d ",srchXXX(1,x,y));
}
return Ratio;
}
希望能帮上你呢Qwq
标签：ch,return,int,模版,线段,基础,sum,id From： https://www.cnblogs.com/DrRatio-DanhengYinyue1007/p/18020777