本文共 5643 字，大约阅读时间需要 18 分钟。

前言

线段树，是一个很好用的能支持O（logn）区间操作的数据结构，随着做一些稍微烦一点的题，有时候会发现有些情况要开一个数组的线段树，更有甚者要树套树，而在很多情况下线段树就不能把所有点都开满了（否则会MLE内存超限），于是就出现了线段树的动态开点写法

基本思想

与普通的线段树相同，动态开点线段树只是一开始每一个节点都没有，insert的时候，如果遇到节点是空的，那么就声明这个点，询问的时候只访问询问的区间中非空节点，这样一来，时间复杂度没有问题还是O（$qlogn$），空间复杂度是O（有过值节点的数量*$logn$）

但是这么做当遇到树套树的时候，空间复杂度就会炸的很惨，为O（有过值的节点的数量*$log^2n$），可能会到O（$n^2log^2n$） 那怎么优化呢，delete的时候如果遇到这个节点的儿子都是空的，那么就删掉这个点，回收这个点的内存，这样空间复杂度就能优化到O（有值节点数量最多时的节点数*$log^2n$）

例题

SDOI2014旅行

题目大意 现在有n个节点的树，每个节点上有个颜色并且有个权值，要求支持： 1.询问树上的一条路径上某颜色的权值和 2.询问树上的一条路径上某颜色的最大权值 3.修改某节点的权值 4.修改某节点的颜色 这一题只要树链剖分，每个颜色都开一棵线段树，支持区间求和和区间max，当然不能开完所以点，只要动态开点就好了 动态开点的打好，可以练一练回收内存的方法，我的方法是开一个vector储存没有用过的内存节点 这个是我的AC代码，我用的是指针

#include
   
    #include
    
     #include
     
      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 registertemplate 
      
        inline T max(const T a,const T b){
  return a>b?a:b;}template 
       
         inline T min(const T a,const T b){
  return a
        
         
           inline T abs(const T a){ return a>0?a:-a;}template 
          
            inline void swap(T&a,T&b){T c=a;a=b;b=c;}template 
           
             inline T gcd(const T a,const T b){ if(a%b==0)return b;return gcd(b,a%b);}template 
            
              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 
             
               void printe(const T x){ if(x>=10)printe(x/10); putchar(x%10+'0');}template 
              
                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]]
               
                std::vector
                
                 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]
                 
                  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]
                  
                   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[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[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
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

结语

动态开点线段树其实是一个很好用的技巧，就算加一个分配、回收内存的东西也不难，具体一定要用分配回收内存的题呢，我做到过，具体在这里我就不介绍了

转载地址：https://blog.csdn.net/zhouyuheng2003/article/details/78871504 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！