学习笔记——线段树系列
线段树
把一个数组存成树形结构，可以处理所有能进行区间合并的操作，单次修改和查询为 \(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.树链剖分
就是把一个树剖成链，作为连续区间在线段树上维护。