线段树进阶 最后更新于 2025-05-01 22:54:35

学了线段树的进阶用法，总结一下板子与一些常用 trick。 # 动态开点线段树 核心思想：**节点在有需要时才被创建**。 若值域为 $n$，操作次数为 $m$，则需要 $O(m \log n)$ 个节点。最多需要 $2n-1$ 个点。 因此，在操作数不多的情况下，这足以支持同时开多颗线段树。 [P3372 【模板】线段树 1](https://www.luogu.com.cn/problem/P3372) ```cpp #include <bits/stdc++.h> #define ls(p) tr[p].l #define rs(p) tr[p].r #define int long long using namespace std; const int INF=0x3f3f3f3f; inline int read() { int w=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { w=(w<<1)+(w<<3)+(ch^48); ch=getchar(); } return w*f; } inline void write(int x) { if(x<0) { putchar('-'); x=-x; } if(x>9) write(x/10); putchar(x%10+'0'); } const int maxn=1e5+10; int n,m,tot; int a[maxn],pre[maxn]; struct node { int l,r,sum,tag; }tr[2000005]; inline void new_node(int &x,int l,int r) { x=++tot; tr[x].sum=pre[r]-pre[l-1]; } inline void pushdown(int p,int l,int r) { int mid=(l+r)>>1; if(tr[p].tag) { if(l!=r) { if(!tr[p].l) new_node(tr[p].l,l,mid); if(!tr[p].r) new_node(tr[p].r,mid+1,r); tr[ls(p)].sum+=(mid-l+1)*tr[p].tag; tr[rs(p)].sum+=(r-(mid+1)+1)*tr[p].tag; tr[ls(p)].tag+=tr[p].tag; tr[rs(p)].tag+=tr[p].tag; } tr[p].tag=0; } } void pushup(int &p,int l,int r) { if(l==r) return; int mid=(l+r)>>1; if(!tr[p].l) new_node(tr[p].l,l,mid),tr[p].l=tot; if(!tr[p].r) new_node(tr[p].r,mid+1,r),tr[p].r=tot; tr[p].sum=tr[ls(p)].sum+tr[rs(p)].sum; } void add(int &p,int l,int r,int L,int R,int k) { if(!p) new_node(p,l,r); if(L<=l&&r<=R) { tr[p].sum+=(r-l+1)*k; tr[p].tag+=k; return; } pushdown(p,l,r); int mid=(l+r)>>1; if(mid>=L) add(ls(p),l,mid,L,R,k); if(mid<R) add(rs(p),mid+1,r,L,R,k); pushup(p,l,r); } int query(int &p,int l,int r,int L,int R) { if(!p) new_node(p,l,r); if(L<=l&&r<=R) { return tr[p].sum; } pushdown(p,l,r); int mid=(l+r)>>1; int sum=0; if(mid>=L) sum+=query(ls(p),l,mid,L,R); if(mid<R) sum+=query(rs(p),mid+1,r,L,R); // pushup(p,l,r); return sum; } int x,y,k,opt,rt; signed main() { #ifndef ONLINE_JUDGE // freopen("in.txt","r",stdin); #endif n=read(),m=read(); for(int i=1;i<=n;++i) { a[i]=read(); pre[i]=pre[i-1]+a[i]; } new_node(rt,1,n); while(m--) { opt=read(); if(opt==1) { x=read(),y=read(),k=read(); add(rt,1,n,x,y,k); } else { x=read(),y=read(); printf("%lld\n",query(rt,1,n,x,y)); } } return 0; } ``` # 可持久化线段树 主要思想是维护上一个版本与当前版本的不同信息，同时这也是它具有一些良好的性质。 性质一：每次修改，只会基于之前版本有从上到下的一条链被修改，即只会增加 $O(\log n)$ 个节点。 性质二：一棵线段树维护了 $[1,l-1]$ 区间的信息，另一棵维护 $[1,r]$ 的信息，那么两者相减就得到了 $[l,r]$ 信息的线段树。 [P3919 【模板】可持久化线段树 1（可持久化数组）](https://www.luogu.com.cn/problem/P3919) ```cpp #include <bits/stdc++.h> #define ls(p) tr[p].l #define rs(p) tr[p].r using namespace std; const int INF=0x3f3f3f3f; inline int read() { int w=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { w=(w<<1)+(w<<3)+(ch^48); ch=getchar(); } return w*f; } inline void write(int x) { if(x<0) { putchar('-'); x=-x; } if(x>9) write(x/10); putchar(x%10+'0'); } const int maxn=1e6+10,maxm=1e6+10; int n,m,a[maxn],tot,rt[maxn]; struct node { int l,r; int val; }tr[31*maxn]; void build(int &p,int l,int r) { p=++tot; if(l==r) { tr[p].val=a[l]; return; } int mid=(l+r)>>1; build(ls(p),l,mid); build(rs(p),mid+1,r); } void update(int pre,int &p,int l,int r,int x,int v) { p=++tot; tr[p]=tr[pre]; if(l==r) { tr[p].val=v; return; } int mid=(l+r)>>1; if(mid>=x) update(ls(pre),ls(p),l,mid,x,v); else update(rs(pre),rs(p),mid+1,r,x,v); } int query(int p,int l,int r,int pos) { if(l==r) { return tr[p].val; } int mid=(l+r)>>1; if(mid>=pos) return query(ls(p),l,mid,pos); else return query(rs(p),mid+1,r,pos); } int v,opt,loc,value; int main() { #ifndef ONLINE_JUDGE //freopen("in.txt","r",stdin); #endif n=read(),m=read(); for(int i=1;i<=n;++i) { a[i]=read(); } build(rt[0],1,n); for(int i=1;i<=m;++i) { v=read(),opt=read(),loc=read(); if(opt==1) { value=read(); update(rt[v],rt[i],1,n,loc,value); } else { rt[i]=rt[v]; printf("%d\n",query(rt[v],1,n,loc)); } } return 0; } ``` 时间复杂度 $O((n+q)\log n)$。 有 $q$ 次修改，至多增加 $\lceil \log n \rceil +1$ 个节点，最坏情况下需要 $2n-1+q(\lceil \log n \rceil +1)$ 个点。 一般情况下时空限制较为宽松，可以直接开 $32$ 倍空间。 [P3834 【模板】可持久化线段树 2](https://www.luogu.com.cn/problem/P3834) 性质二的完美应用。 ```cpp #include <bits/stdc++.h> #define ls(p) tr[p].l #define rs(p) tr[p].r using namespace std; const int INF=0x3f3f3f3f; inline int read() { int w=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { w=(w<<1)+(w<<3)+(ch^48); ch=getchar(); } return w*f; } inline void write(int x) { if(x<0) { putchar('-'); x=-x; } if(x>9) write(x/10); putchar(x%10+'0'); } const int maxn=2e5+10; int n,m,a[maxn],tmp[maxn],len,tot; int rt[maxn]; struct node { int l,r,sum; }tr[maxn<<5]; void build(int &p,int l,int r) { p=++tot; if(l==r) { tr[p].sum=0; return; } int mid=(l+r)>>1; build(ls(p),l,mid); build(rs(p),mid+1,r); } void update(int pre,int &p,int l,int r,int x) { p=++tot,tr[p]=tr[pre],tr[p].sum+=1; if(l==r) return; int mid=(l+r)>>1; if(mid>=x) update(ls(pre),ls(p),l,mid,x); else update(rs(pre),rs(p),mid+1,r,x); } int query(int pre,int p,int l,int r,int k) { if(l==r) return l; int mid=(l+r)>>1,x=tr[tr[p].l].sum-tr[tr[pre].l].sum; if(x>=k) return query(ls(pre),ls(p),l,mid,k); return query(rs(pre),rs(p),mid+1,r,k-x); } int main() { #ifndef ONLINE_JUDGE //freopen("in.txt","r",stdin); #endif n=read(),m=read(); for(int i=1;i<=n;++i) { tmp[i]=a[i]=read(); } sort(tmp+1,tmp+n+1); len=unique(tmp+1,tmp+n+1)-tmp-1; build(rt[0],1,len); for(int i=1;i<=n;++i) { a[i]=lower_bound(tmp+1,tmp+len+1,a[i])-tmp; update(rt[i-1],rt[i],1,len,a[i]); } for(int i=1,l,r,k;i<=m;++i) { l=read(),r=read(),k=read(); int ans=query(rt[l-1],rt[r],1,len,k); cout<<tmp[ans]<<endl; } return 0; } ``` [P3168 [CQOI2015] 任务查询系统](https://www.luogu.com.cn/problem/P3168) 涉及到一些 trick： 1. 每个任务转化为一次差分操作，在时刻 $s_i$ 添加任务，$e_i+1$ 删除任务。 2. 将值域（优先级）离散化，建立可持久化权值线段树，每个区间维护出现次数与优先级总和 3. 于是即求区间前 $k$ 大的和，类比静态区间第 $k$ 大问题。 [P4137 Rmq Problem / mex](https://www.luogu.com.cn/problem/P4137)