线段树
把一个数组存成树形结构，可以处理所有能进行区间合并的操作，单次修改和查询为 \(O(\log n)\)。
1.普通线段树
学会使用懒标记，放个板子。
支持单点和区间的加法与乘法，单点查询和区间查询最值与求和。
点击查看代码
int n,q;
ll a[maxn];
struct SegmentTree{
#define len (r-l+1)
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define llen (mid-l+1)
#define rlen (r-mid)
ll maxval[maxm],minval[maxm],sumval[maxm];
ll addlaz[maxm],mullaz[maxm];
inline void push_up(int rt){
maxval[rt]=max(maxval[rt<<1],maxval[rt<<1|1]);
minval[rt]=min(minval[rt<<1],minval[rt<<1|1]);
sumval[rt]=(sumval[rt<<1]+sumval[rt<<1|1])%mod;
return;
}
inline void push_down(int rt,int l,int r){
if(!addlaz[rt]&&mullaz[rt]==1) return;
sumval[rt<<1]=(sumval[rt<<1]*mullaz[rt]+addlaz[rt]*llen)%mod;
sumval[rt<<1|1]=(sumval[rt<<1|1]*mullaz[rt]+addlaz[rt]*rlen)%mod;
maxval[rt<<1]=(maxval[rt<<1]*mullaz[rt]+addlaz[rt])%mod;
maxval[rt<<1|1]=(maxval[rt<<1|1]*mullaz[rt]+addlaz[rt])%mod;
minval[rt<<1]=(minval[rt<<1]*mullaz[rt]+addlaz[rt])%mod;
minval[rt<<1|1]=(minval[rt<<1|1]*mullaz[rt]+addlaz[rt])%mod;
addlaz[rt<<1]=(addlaz[rt<<1]*mullaz[rt]+addlaz[rt])%mod;
addlaz[rt<<1|1]=(addlaz[rt<<1|1]*mullaz[rt]+addlaz[rt])%mod;
mullaz[rt<<1]=mullaz[rt<<1]*mullaz[rt]%mod;
mullaz[rt<<1|1]=mullaz[rt<<1|1]*mullaz[rt]%mod;
addlaz[rt]=0,mullaz[rt]=1;
return;
}
inline void build(int rt,int l,int r){
if(l==r){
maxval[rt]=minval[rt]=sumval[rt]=a[l];
return;
}
build(lson); build(rson);
addlaz[rt]=0,mullaz[rt]=1;
push_up(rt);
}
inline void update_add_x(int rt,int l,int r,int p,ll k){
if(l==r){
maxval[rt]=(maxval[rt]+k)%mod;
minval[rt]=(minval[rt]+k)%mod;
sumval[rt]=(sumval[rt]+k)%mod;
return;
}
push_down(rt,l,r);
if(p<=mid) update_add_x(lson,p,k);
else update_add_x(rson,p,k);
push_up(rt);
}
inline void update_add_lr(int rt,int l,int r,int pl,int pr,ll k){
if(pl<=l&&r<=pr){
maxval[rt]=(maxval[rt]+k)%mod;
minval[rt]=(minval[rt]+k)%mod;
sumval[rt]=(sumval[rt]+k*len)%mod;
addlaz[rt]=(addlaz[rt]+k)%mod;
return;
}
push_down(rt,l,r);
if(pl<=mid) update_add_lr(lson,pl,pr,k);
if(pr>mid) update_add_lr(rson,pl,pr,k);
push_up(rt);
}
inline void update_mul_x(int rt,int l,int r,int p,ll k){
if(l==r){
maxval[rt]=maxval[rt]*k%mod;
minval[rt]=minval[rt]*k%mod;
sumval[rt]=sumval[rt]*k%mod;
return;
}
push_down(rt,l,r);
if(p<=mid) update_mul_x(lson,p,k);
else update_mul_x(rson,p,k);
push_up(rt);
}
inline void update_mul_lr(int rt,int l,int r,int pl,int pr,ll k){
if(pl<=l&&r<=pr){
maxval[rt]=maxval[rt]*k%mod;
minval[rt]=minval[rt]*k%mod;
sumval[rt]=sumval[rt]*k%mod;
addlaz[rt]=addlaz[rt]*k%mod;
mullaz[rt]=mullaz[rt]*k%mod;
return;
}
push_down(rt,l,r);
if(pl<=mid) update_mul_lr(lson,pl,pr,k);
if(pr>mid) update_mul_lr(rson,pl,pr,k);
push_up(rt);
}
inline ll query_val_x(int rt,int l,int r,int p){
if(l==r) return sumval[rt];
push_down(rt,l,r);
if(p<=mid) return query_val_x(lson,p);
else return query_val_x(rson,p);
}
inline ll query_max_lr(int rt,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr) return maxval[rt];
push_down(rt,l,r);
ll res=-0x3f3f3f3f3f3f3f3f;
if(pl<=mid) res=max(res,query_max_lr(lson,pl,pr));
if(pr>mid) res=max(res,query_max_lr(rson,pl,pr));
return res;
}
inline ll query_min_lr(int rt,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr) return minval[rt];
push_down(rt,l,r);
ll res=0x3f3f3f3f3f3f3f3f;
if(pl<=mid) res=min(res,query_min_lr(lson,pl,pr));
if(pr>mid) res=min(res,query_min_lr(rson,pl,pr));
return res;
}
inline ll query_sum_lr(int rt,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr) return sumval[rt];
push_down(rt,l,r);
ll res=0;
if(pl<=mid) res+=query_sum_lr(lson,pl,pr);
if(pr>mid) res+=query_sum_lr(rson,pl,pr);
return res%mod;
}
}sgt;
int main(){
n=read(),q=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
sgt.build(1,1,n);
while(q--){
int ope=read();
ll res;
if(ope==1){
int x=read(); ll k=read();
sgt.update_add_x(1,1,n,x,k);
}
else if(ope==2){
int l=read(),r=read(); ll k=read();
sgt.update_add_lr(1,1,n,l,r,k);
}
else if(ope==3){
int x=read(); ll k=read();
sgt.update_mul_x(1,1,n,x,k);
}
else if(ope==4){
int l=read(),r=read(); ll k=read();
sgt.update_mul_lr(1,1,n,l,r,k);
}
else if(ope==5){
int l=read(),r=read();
res=sgt.query_max_lr(1,1,n,l,r);
printf("%lld\n",res);
}
else if(ope==6){
int l=read(),r=read();
res=sgt.query_min_lr(1,1,n,l,r);
printf("%lld\n",res);
}
else if(ope==7){
int l=read(),r=read();
res=sgt.query_sum_lr(1,1,n,l,r);
printf("%lld\n",res);
}
else if(ope==8){
int x=read();
res=sgt.query_val_x(1,1,n,x);
printf("%lld\n",res);
}
}
return 0;
}
2.树链剖分
就是把一个树按照一定顺序剖分成链，作为连续区间在线段树上维护。
3.权值线段树
离散化版本
将所有操作离线，离散化后得到每个数据对应到下标，把这些数据放到线段树中去维护。
模板是平衡树的模板题，需要卡一卡才能过掉（这个版本是没卡的）
点击查看代码
int n,opt[maxn],a[maxn];
vector<int> v;
int tot;
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int siz[maxm];
inline void push_up(int rt){
siz[rt]=siz[rt<<1]+siz[rt<<1|1];
}
inline void build(int rt,int l,int r){
siz[rt]=0;
if(l==r) return;
build(lson),build(rson);
}
inline void update(int rt,int l,int r,int p,int k){
if(l==r){
siz[rt]+=k;
return;
}
if(p<=mid) update(lson,p,k);
else update(rson,p,k);
push_up(rt);
}
inline int query(int rt,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr){
return siz[rt];
}
int res=0;
if(pl<=mid) res+=query(lson,pl,pr);
if(pr>mid) res+=query(rson,pl,pr);
return res;
}
inline int kth(int rt,int l,int r,int k){
if(l==r){
return l;
}
if(k<=siz[rt<<1]) return kth(lson,k);
else return kth(rson,k-siz[rt<<1]);
}
}tree;
int main(){
n=read();
for(int i=1;i<=n;i++){
opt[i]=read(),a[i]=read();
v.push_back(a[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
tot=v.size();
for(int i=1;i<=n;i++){
if(opt[i]!=4){
a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
}
if(opt[i]==1) tree.update(1,1,tot,a[i],1);
if(opt[i]==2) tree.update(1,1,tot,a[i],-1);
if(opt[i]==3) printf("%d\n",tree.query(1,1,tot,1,a[i]-1)+1);
if(opt[i]==4) printf("%d\n",v[tree.kth(1,1,tot,a[i])-1]);
if(opt[i]==5){
int pre=tree.query(1,1,tot,1,a[i]-1);
printf("%d\n",v[tree.kth(1,1,tot,pre)-1]);
}
if(opt[i]==6){
int nxt=tree.query(1,1,tot,1,a[i]);
printf("%d\n",v[tree.kth(1,1,tot,nxt+1)-1]);
}
}
return 0;
}