前言

線段樹，是一個(gè)很好用的能支持O（logn）區(qū)間操作的數(shù)據(jù)結(jié)構(gòu)，隨著做一些稍微煩一點(diǎn)的題，有時(shí)候會(huì)發(fā)現(xiàn)有些情況要開一個(gè)數(shù)組的線段樹，更有甚者要樹套樹，而在很多情況下線段樹就不能把所有點(diǎn)都開滿了（否則會(huì)MLE內(nèi)存超限），于是就出現(xiàn)了線段樹的動(dòng)態(tài)開點(diǎn)寫法

基本思想

與普通的線段樹相同，動(dòng)態(tài)開點(diǎn)線段樹只是一開始每一個(gè)節(jié)點(diǎn)都沒有，insert的時(shí)候，如果遇到節(jié)點(diǎn)是空的，那么就聲明這個(gè)點(diǎn)，詢問的時(shí)候只訪問詢問的區(qū)間中非空節(jié)點(diǎn)，這樣一來，時(shí)間復(fù)雜度沒有問題還是O（qlogn），空間復(fù)雜度是O（有過值節(jié)點(diǎn)的數(shù)量*logn）
但是這么做當(dāng)遇到樹套樹的時(shí)候，空間復(fù)雜度就會(huì)炸的很慘，為O（有過值的節(jié)點(diǎn)的數(shù)量*log2n），可能會(huì)到O（n2log2n）
那怎么優(yōu)化呢，delete的時(shí)候如果遇到這個(gè)節(jié)點(diǎn)的兒子都是空的，那么就刪掉這個(gè)點(diǎn)，回收這個(gè)點(diǎn)的內(nèi)存，這樣空間復(fù)雜度就能優(yōu)化到O（有值節(jié)點(diǎn)數(shù)量最多時(shí)的節(jié)點(diǎn)數(shù)*log2n）

例題

SDOI2014旅行
https://www.luogu.org/problemnew/show/3313
題目大意
現(xiàn)在有n個(gè)節(jié)點(diǎn)的樹，每個(gè)節(jié)點(diǎn)上有個(gè)顏色并且有個(gè)權(quán)值，要求支持：
1.詢問樹上的一條路徑上某顏色的權(quán)值和
2.詢問樹上的一條路徑上某顏色的最大權(quán)值
3.修改某節(jié)點(diǎn)的權(quán)值
4.修改某節(jié)點(diǎn)的顏色
這一題只要樹鏈剖分，每個(gè)顏色都開一棵線段樹，支持區(qū)間求和和區(qū)間max，當(dāng)然不能開完所以點(diǎn)，只要?jiǎng)討B(tài)開點(diǎn)就好了
動(dòng)態(tài)開點(diǎn)的打好，可以練一練回收內(nèi)存的方法，我的方法是開一個(gè)vector儲(chǔ)存沒有用過的內(nèi)存節(jié)點(diǎn)
這個(gè)是我的AC代碼，我用的是指針

#include<cstdio> #include<cstring> #include<cctype> namespace fast_IO {const int IN_LEN=10000000,OUT_LEN=10000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf;char *lastin=ibuf+IN_LEN;const char *lastout=ibuf+OUT_LEN-1;inline char getchar_(){if(ih==lastin)lastin=ibuf+fread(ibuf,1,IN_LEN,stdin),ih=ibuf;return (*ih++);}inline void putchar_(const char x){if(ih==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf, 1, oh - obuf, stdout);} } using namespace fast_IO; //#define getchar() getchar_() //#define putchar(x) putchar_((x)) typedef long long LL; #define rg register template <typename T> inline T max(const T a,const T b){return a>b?a:b;} template <typename T> inline T min(const T a,const T b){return a<b?a:b;} template <typename T> inline T abs(const T a){return a>0?a:-a;} template <typename T> inline void swap(T&a,T&b){T c=a;a=b;b=c;} template <typename T> inline T gcd(const T a,const T b){if(a%b==0)return b;return gcd(b,a%b);} template <typename T> inline void read(T&x) {char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x; } template <typename T> void printe(const T x) {if(x>=10)printe(x/10);putchar(x%10+'0'); } template <typename T> inline void print(const T x) {if(x<0)putchar('-'),printe(-x);else printe(x); } const int MAX=524288,MAXN=100007,MAXM=200007; int n,m,q; int head[MAXN],nxt[MAXM],tow[MAXM],tmp=1; inline void addb(const int a,const int b) {tmp++;nxt[tmp]=head[a];head[a]=tmp;tow[tmp]=b; } int v[MAXN],fr[MAXN],fa[MAXN],size[MAXN],dep[MAXN],tim=0,son[MAXN],top[MAXN],tid[MAXN],bak[MAXN]; void dfs1(const int u,int las,int depth) {fa[u]=las;dep[u]=depth;size[u]=1;for(rg int i=head[u];~i;i=nxt[i]){const int v=tow[i];if(v!=las){dfs1(v,u,depth+1);size[u]+=size[v];if(son[u]==-1||size[son[u]]<size[v])son[u]=v;}} } void dfs2(const int u,const int tp) {top[u]=tp;tid[u]=++tim;bak[tim]=u;if(son[u]==-1)return;dfs2(son[u],tp);for(rg int i=head[u];~i;i=nxt[i]){int v=tow[i];if(v!=fa[u]&&v!=son[u])dfs2(v,v);} } int l[MAX],r[MAX],mid[MAX]; struct node {node *lson,*rson;int irt,maxx; }Q[2000001],*root[100001]; #include<vector> std::vector<node*>bin; inline node *new_node() {node *res=bin[bin.size()-1];bin.pop_back();res->lson=res->rson=0;res->irt=res->maxx=0;return res; } inline void del_node(node *res) {bin.push_back(res); } void ini(const int root,const int ll,const int rr) {l[root]=ll,mid[root]=(ll+rr)>>1,r[root]=rr;if(ll==rr)return;ini(root<<1,ll,mid[root]),ini(root<<1|1,mid[root]+1,rr); } inline void update(node *ROOT) {ROOT->irt=ROOT->maxx=0;if(ROOT->lson)ROOT->irt+=ROOT->lson->irt,ROOT->maxx=max(ROOT->maxx,ROOT->lson->maxx);if(ROOT->rson)ROOT->irt+=ROOT->rson->irt,ROOT->maxx=max(ROOT->maxx,ROOT->rson->maxx); } void insert(node *ROOT,const int root,const int wan,const int ins) {if(l[root]==r[root]){ROOT->irt=ins,ROOT->maxx=ins;return;}if(wan<=mid[root]){if(!ROOT->lson)ROOT->lson=new_node();insert(ROOT->lson,root<<1,wan,ins);}else{if(!ROOT->rson)ROOT->rson=new_node();insert(ROOT->rson,root<<1|1,wan,ins);}update(ROOT); } node *del(node *ROOT,const int root,const int wan) {if(l[root]==r[root]){del_node(ROOT);return 0;}if(wan<=mid[root]){ROOT->lson=del(ROOT->lson,root<<1,wan);if(ROOT->lson==0&&ROOT->rson==0){del_node(ROOT);return 0;}}else{ROOT->rson=del(ROOT->rson,root<<1|1,wan);if(ROOT->lson==0&&ROOT->rson==0){del_node(ROOT);return 0;}}update(ROOT);return ROOT; } int search_irt(node *ROOT,const int root,const int ll,const int rr) {if(l[root]==ll&&r[root]==rr)return ROOT->irt;if(mid[root]>=rr){if(ROOT->lson)return search_irt(ROOT->lson,root<<1,ll,rr);return 0;}else if(mid[root]<ll){if(ROOT->rson)return search_irt(ROOT->rson,root<<1|1,ll,rr);return 0;}else{int res=0;if(ROOT->lson)res+=search_irt(ROOT->lson,root<<1,ll,mid[root]);if(ROOT->rson)res+=search_irt(ROOT->rson,root<<1|1,mid[root]+1,rr);return res;} } int search_maxx(node *ROOT,const int root,const int ll,const int rr) {if(l[root]==ll&&r[root]==rr)return ROOT->maxx;if(mid[root]>=rr){if(ROOT->lson)return search_maxx(ROOT->lson,root<<1,ll,rr);return 0;}else if(mid[root]<ll){if(ROOT->rson)return search_maxx(ROOT->rson,root<<1|1,ll,rr);return 0;}else{int res=0;if(ROOT->lson)res=max(res,search_maxx(ROOT->lson,root<<1,ll,mid[root]));if(ROOT->rson)res=max(res,search_maxx(ROOT->rson,root<<1|1,mid[root]+1,rr));return res;} } inline int ssearch_irt(node *ROOT,int a,int b) {int s=0;while(top[a]!=top[b]){if(dep[top[a]]<dep[top[b]])swap(a,b);s=s+search_irt(ROOT,1,tid[top[a]],tid[a]);a=fa[top[a]];}if(dep[a]>dep[b])swap(a,b);s=s+search_irt(ROOT,1,tid[a],tid[b]);return s; } inline int ssearch_maxx(node *ROOT,int a,int b) {int s=0;while(top[a]!=top[b]){if(dep[top[a]]<dep[top[b]])swap(a,b);s=max(s,search_maxx(ROOT,1,tid[top[a]],tid[a]));a=fa[top[a]];}if(dep[a]>dep[b])swap(a,b);s=max(s,search_maxx(ROOT,1,tid[a],tid[b]));return s; } inline char get_char() {char cu=getchar();while(cu<'A'&&cu>'Z')cu=getchar();return cu; } inline int getopt() {char a=get_char(),b=get_char();if(a=='C'){if(b=='C')return 1;return 2;}else{if(b=='S')return 3;return 4;} } int main() {memset(head,-1,sizeof(head));memset(son,-1,sizeof(son));read(n),read(q);ini(1,1,n);for(rg int i=0;i<=2000000;i++)bin.push_back(&Q[i]);for(rg int i=1;i<=100000;i++)root[i]=new_node();for(rg int i=1;i<=n;i++)read(v[i]),read(fr[i]);for(rg int i=1;i<n;i++){int a,b;read(a),read(b);addb(a,b),addb(b,a);}dfs1(1,0,1),dfs2(1,1);for(rg int i=1;i<=n;i++)insert(root[fr[i]],1,tid[i],v[i]);for(rg int i=1;i<=q;i++){int opt=getopt(),ll,rr;read(ll),read(rr);if(opt==1){del(root[fr[ll]],1,tid[ll]);if(root[fr[ll]]==0)root[fr[ll]]=new_node();fr[ll]=rr;insert(root[fr[ll]],1,tid[ll],v[ll]);}else if(opt==2){v[ll]=rr;insert(root[fr[ll]],1,tid[ll],v[ll]);}else if(opt==3)print(ssearch_irt(root[fr[ll]],ll,rr)),putchar('\n');else print(ssearch_maxx(root[fr[ll]],ll,rr)),putchar('\n');}return flush(),0; }

結(jié)語

動(dòng)態(tài)開點(diǎn)線段樹其實(shí)是一個(gè)很好用的技巧，就算加一個(gè)分配、回收內(nèi)存的東西也不難，具體一定要用分配回收內(nèi)存的題呢，我做到過，具體在這里我就不介紹了

總結(jié)

以上是生活随笔為你收集整理的动态开点线段树(多棵线段树）的内存分配与回收的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。