线段树算是树状数组的进阶版了，树状数组能做的，线段树也肯定能做，它做不了的，线段树也能做。
但确实线段树的代码量也很让人挠头，基本原理不再解释。
先看一下基础的模板吧
单点修改和区间查询
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=300000;
int n,m;
int a[N];
#define lson (rt<<1)
#define rson (rt<<1|1)
struct lmy
{
int l,r;
int sum,max;
}tr[N<<2];
void build(int rt,int l,int r)//建树
{
tr[rt].l=l;
tr[rt].r=r;
if(l==r)
{
tr[rt].sum=a[l];
tr[rt].max=a[l];
return ;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
tr[rt].sum=tr[lson].sum+tr[rson].sum;
tr[rt].max=max(tr[lson].max,tr[rson].max);
}
void update(int rt,int k,int val)//单点修改
{
if(tr[rt].l==tr[rt].r)
{
tr[rt].sum+=val;
tr[rt].max+=val;
return ;
}
int mid=(tr[rt].l+tr[rt].r)>>1;
if(k<=mid)
{
update(lson,k,val);
}
if(k>mid)
{
update(rson,k,val);
}
tr[rt].sum=tr[lson].sum+tr[rson].sum;
tr[rt].max=max(tr[lson].max,tr[rson].max);
}
int query1(int rt,int l,int r)//区间查询,求和
{
if(l<=tr[rt].l&&r>=tr[rt].r)
{
return tr[rt].sum;
}
int mid=(tr[rt].l+tr[rt].r)>>1;
int val=0;
if(l<=mid)
{
val+=query1(lson,l,r);
}
if(r>mid)
{
val+=query1(rson,l,r);
}
return val;
}
int query2(int rt,int l,int r)//区间求max
{
if(l<=tr[rt].l&&r>=tr[rt].r)
{
return tr[rt].max;
}
int mid=(tr[rt].l+tr[rt].r)>>1;
int val=0;
if(l<=mid)
{
val=max(val,query2(lson,l,r));
}
if(r>mid)
{
val=max(val,query2(rson,l,r));
}
return val;
}
int main()
{
scanf("%d",&n);
if(n!=0)
{
build(1,1,n);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
update(1,i,a[i]);
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
char op[3];
scanf("%s",op);
if(op[0]=='A')
{
int k,val;
scanf("%d%d",&k,&val);
update(1,k,val);
}
if(op[0]=='S')
{
int l,r;
scanf("%d%d",&l,&r);
int ans=query1(1,l,r);
printf("%d\n",ans);
}
}
}
区间修改和区间查询
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=300000;
int n,m;
int a[N];
#define lson (rt<<1)
#define rson (rt<<1|1)
struct lmy
{
int l,r;
int sum;
int lazy;//延时标记
}tr[N<<2];
void pushdown(int rt)//延时标记下放到左右子树
{
if(tr[rt].lazy)
{
int lz=tr[rt].lazy;
tr[rt].lazy=0;
tr[lson].lazy+=lz;
tr[rson].lazy+=lz;
tr[lson].sum+=lz*(tr[lson].r-tr[lson].l+1);
tr[rson].sum+=lz*(tr[rson].r-tr[rson].l+1);
}
}
void build(int rt,int l,int r)//建树
{
tr[rt].l=l;
tr[rt].r=r;
if(tr[rt].l==tr[rt].r)
{
tr[rt].sum=a[l];
return ;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
tr[rt].sum=tr[lson].sum+tr[rson].sum;
}
void update(int rt,int l,int r,int val)//区间修改
{
if(l<=tr[rt].l&&r>=tr[rt].r)
{
tr[rt].lazy+=val;
tr[rt].sum+=val*(tr[rt].r-tr[rt].l+1);
return ;
}
pushdown(rt);
int mid=(tr[rt].l+tr[rt].r)>>1;
if(l<=mid)
{
update(lson,l,r,val);
}
if(r>mid)
{
update(rson,l,r,val);
}
tr[rt].sum=tr[lson].sum+tr[rson].sum;
}
int query(int rt,int l,int r)//区间查询
{
if(l<=tr[rt].l&&tr[rt].r<=r)
{
return tr[rt].sum;
}
pushdown(rt);
int mid=(tr[rt].l+tr[rt].r)>>1;
int val=0;
if(l<=mid)
{
val+=query(lson,l,r);
}
if(r>mid)
{
val+=query(rson,l,r);
}
return val;
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
build(1,1,n);
scanf("%lld",&m);
for(int i=1;i<=m;i++)
{
char s[3];
scanf("%s",s);
if(s[0]=='S')
{
int l,r;
scanf("%lld%lld",&l,&r);
printf("%lld\n",query(1,l,r));
}
if(s[0]=='A')
{
int l,r,val;
scanf("%lld%lld%lld",&l,&r,&val);
update(1,l,r,val);
}
}
}
这里运用了一个延时标记，是为了节省时间的开销，每次只更新到所需的区间，如果还需要再下一层的区间就把延时标记下放。
看一个比较简单的应用
忠诚
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=300000;
int n,m;
int a[N];
#define lson (rt<<1)
#define rson (rt<<1|1)
struct lmy
{
int l,r;
int min;
}tr[N<<2];
void build(int rt,int l,int r)
{
tr[rt].l=l;
tr[rt].r=r;
if(tr[rt].l==tr[rt].r)
{
tr[rt].min=a[l];
return ;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
tr[rt].min=min(tr[lson].min,tr[rson].min);
}
int query(int rt,int l,int r)
{
if(l<=tr[rt].l&&r>=tr[rt].r)
{
return tr[rt].min;
}
int val=0x3f3f3f3f;
int mid=(tr[rt].l+tr[rt].r)>>1;
if(l<=mid)
{
val=min(val,query(lson,l,r));
}
if(r>mid)
{
val=min(val,query(rson,l,r));
}
return val;
}
int main()
{
memset(tr,0x3f,sizeof(tr));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
build(1,1,n);
for(int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
int ans=query(1,l,r);
printf("%d ",ans);
}
}