线段树一般用于维护符合结合律的信息。可以用于求区间最大值 区间和 区间最小值 最大子段和甚至于最大负数最小正数之类的信息。事实上线段树只有你想不到，很少有做不到的，算是相当常用的数据结构。
下面将结合个人理解和具体题目来讲一讲线段树。
[https://www.luogu.com.cn/problem/P8818](csps2022 策略游戏)
仔细分析，这是个非常烦的例题，不仅要判断中间是否有零，还要判断最小正数和最大正数，线段树也可以维护这些如此繁琐的信息。
https://www.luogu.com.cn/blog/novax13/game-solution
#include <cstdio>
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define ls(p) ((p)<<1)
#define rs(p) (((p)<<1)|1)
const int Nx=100010;
int N,M,Q,A[Nx],B[Nx];
struct node{long long maz,miz,maf,mif,zro;};
node As[4*Nx],Bs[4*Nx];
void pushnode(node &a,int val)
{
if(val==0)
a.zro=1;
else if(val>0)
a.maz=a.miz=val;
else if(val<0)
a.maf=a.mif=val;
}
node merge(node x,node y)
{
node ret;
ret.zro=x.zro||y.zro;
if(!x.maz||!y.maz)
{
ret.maz=x.maz+y.maz;
ret.miz=x.miz+y.miz;
}
else
{
ret.maz=max(x.maz,y.maz);
ret.miz=min(x.miz,y.miz);
}
if(!x.maf||!y.maf)
{
ret.maf=x.maf+y.maf;
ret.mif=x.mif+y.mif;
}
else
{
ret.maf=max(x.maf,y.maf);
ret.mif=min(x.mif,y.mif);
}
return ret;
}
void build(int ll,int rr,int p,node seg[],int C[])
{
if(ll==rr)
{
pushnode(seg[p],C[ll]);
return;
}
int mid=(ll+rr)>>1;
build(ll,mid,ls(p),seg,C);
build(mid+1,rr,rs(p),seg,C);
seg[p]=merge(seg[ls(p)],seg[rs(p)]);
}
node query(int ll,int rr,int p,int L,int R,node seg[])
{
if(L<=ll&&rr<=R)
return seg[p];
int mid=(ll+rr)>>1;
if(L>mid)
return query(mid+1,rr,rs(p),L,R,seg);
if(R<=mid)
return query(ll,mid,ls(p),L,R,seg);
return merge(query(ll,mid,ls(p),L,R,seg),query(mid+1,rr,rs(p),L,R,seg));
}
long long get_ans(node ax,node bx)
{
long long ret;
//printf("%d %d %d %d %d %d %d %d %d %d\n",ax.maz,ax.miz,ax.maf,ax.mif,ax.zro,bx.maz,bx.miz,bx.maf,bx.mif,bx.zro);
if(bx.mif!=0&&bx.miz==0)//后手无正数
{
if(ax.mif!=0)//先手有负数
ret=(bx.zro)?0:ax.mif*bx.maf;
else//先手无负数
ret=(ax.zro)?0:ax.miz*bx.mif;
}
else if(bx.mif==0&&bx.miz!=0)//后手无负数
{
if(ax.miz!=0)//先手有正数
ret=(bx.zro)?0:ax.maz*bx.miz;
else//先手无正数
ret=(ax.zro)?0:ax.maf*bx.maz;
}
else//后手正负都有/后手只有0
{
if(ax.zro)
ret=0;
else if(ax.mif!=0&&ax.miz==0)//先手无正数
ret=ax.maf*bx.maz;
else if(ax.mif==0&&ax.miz!=0)//先手无负数
ret=ax.miz*bx.mif;
else//先手正负都有
ret=max(ax.miz*bx.mif,ax.maf*bx.maz);
}
return ret;
}
int main()
{
scanf("%d%d%d",&N,&M,&Q);
int i,j,k,la,ra,lb,rb;
for(i=1;i<=N;i++)
scanf("%d",&A[i]);
for(i=1;i<=M;i++)
scanf("%d",&B[i]);
build(1,N,1,As,A);
build(1,M,1,Bs,B);
node ax,bx;
while(Q--)
{
scanf("%d%d%d%d",&la,&ra,&lb,&rb);
ax=query(1,N,1,la,ra,As);
bx=query(1,M,1,lb,rb,Bs);
printf("%lld\n",get_ans(ax,bx));
}
}
这是普通线段树，接下来讲一种功能更加强大的线段树，动态开点线段树。
[https://www.luogu.com.cn/problem/P3960](NOIP2017 列队)
题目要求我们建立一个数据结构，支持将一个数放到尾部，以及查询当前第k个数。并做到删除。
直接建树时间会很爆炸，不如我们维护一个01序列，0表示当前没有，1表示当前有。如此建立一个动态开点线段树。
1-n/1-m的数字很好维护，我们开个vector记录后面添加的数即可。
https://www.luogu.com.cn/blog/Peterprpr/solution-p3960
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ri register int
const int N=3e5+5;
ll num[N<<1] ,rt[N],n,m,q;
ll cnt=1;
ll ls[N<<5],rs[N<<5],sum[N<<5];
int query(ll &p,ll l,ll r,ll x){
if(!p) p=++cnt,sum[p]=r-l+1;
sum[p]--;
if(l==r){
return l;
}
ll mid=l+r>>1,k;
if(!ls[p]) k=mid-l+1;
else k=sum[ls[p]];
if(x<=k) return query(ls[p],l,mid,x);
else return query(rs[p],mid+1,r,x-k);
}
vector<ll> g[N];
int main(){
std::ios::sync_with_stdio(false);
cin>>n>>m>>q;
ll len=max(n,m)+q;
for(ri i=1;i<=n;i++) num[i]=i*m;
for(ri i=1;i<=q;i++){
ll x,y;
cin>>x>>y;
if(y==m){
ll ans=query(rt[n+1],1,len,x);
num[i+n]=num[ans];
}
else{
ll ans=query(rt[n+1],1,len,x);
g[x].push_back(num[ans]);
ans=query(rt[x],1,len,y);
if(ans>=m) num[i+n]=g[x][ans-m];
else num[i+n]=ans+m*(x-1);
}
cout<<num[i+n]<<endl;
}
}
上面的话是用动态开点线段树+vector维护一段序列，那么接下来应该是最厉害的应用。
动态开点权值线段树
首先是求逆序对。和树状数组一样，不表。
其次是这道题。
https://www.luogu.com.cn/problem/P5459
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ri register int
const ll N=1e5+5;
ll len=N*N;
ll a[N],n,L,R,cnt=1,sum[N<<6];
int ls[N<<6],rs[N<<6],rt;
void insert(int&p,ll l,ll r,ll x){
if(!p) p=++cnt;
sum[p]++;
if(l==r) return ;
ll mid=l+r>>1;
if(x<=mid) insert(ls[p],l,mid,x);
else insert(rs[p],mid+1,r,x);
}
ll query(int&p,ll l,ll r,ll nl,ll nr){
if(!p) p=++cnt;//以后询问时也可以动态开点记住了
if(nl<=l&&r<=nr){
return sum[p];
}
ll ans=0,mid=l+r>>1;
if(nl<=mid) ans+=query(ls[p],l,mid,nl,nr);
if(nr>mid) ans+=query(rs[p],mid+1,r,nl,nr);
return ans;
}
int main(){
std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>L>>R;
for(ri i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
ll res=0;
for(ri i=1;i<=n;i++){
insert(rt,-len,len,a[i-1]);
ll l=a[i]-R,r=a[i]-L;
res+=query(rt,-len,len,l,r);
//cout<<query(rt,-len,len,l,r)<<endl;
}
cout<<res;
}
主席树
又称为可持久化权值线段树。发明人黄嘉泰原话：对于原序列的每一个前缀[1···i]建立出一棵线段树维护值域上每个数出现的次数，则其树是可减的。
例题以后再补。