博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
三个半小时考试，三个小时调试-----巨容易写炸的nlogn数据结构专题
阅读量：6152 次
发布时间：2019-06-21

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

1.树状数组

         这个是最最最简单的nlogn的数据结构啦，非常好写也不容易写错（就算写错也比较容易检查）

         相比其他bt的数据结构，树状数组的代码非常简洁，就是c数组有点抽象，晦涩难懂

         主要用来单点修改，区间查询。也可以通过差分来进行区间修改和区间查询，但一般区间修改一般不止加加减减这么简单啦，所以区间修改还是线段树会比较常用。

         总体还是很easy的，不多bb直接粘代码

    

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define maxn 600000#define inf 0x7fffffusing namespace std;int n,m,x,y,k,op;int a[maxn],c[maxn];int read(){ int xx=0,kk=1;char p=' '; while(!isdigit(p)){p=getchar();if(p=='-')kk=-1;} while(isdigit(p)){xx=xx*10+p-'0';p=getchar();} return kk*xx;}int lowbit(int x){ return x&-x;}void add(int x,int k){ while(x<=n) { c[x]+=k; x+=lowbit(x); }}int query(int x){ int ans=0; while(x) { ans+=c[x]; x-=lowbit(x); } return ans;}int main(){ n=read();m=read(); for(int i=1;i<=n;++i) a[i]=read(),add(i,a[i]); //注意一开始给c数组赋值 for(int j=1;j<=m;++j) { op=read();x=read(); switch(op) { case 1:k=read();add(x,k);break; case 2:y=read();printf("%lld\n",query(y)-query(x-1));break; } } return 0;}

 

2.线段树

         又臭又长的数据结构的开端，一开始觉得线段树好长啊，好难写啊，好烦啊怎么这么多函数啊，啊我怎么又写炸啦。现在回过头来看线段树，真的是非常良心的一个数据结构啦！

        线段树的用途很多，当然很多都是想不到的（现在出题人真的丧心病狂，什么神学操作都有= =）

        相比起treap和splay线段树真的是太好写了（暴风哭泣），比起树状数组又好理解并且实用性广一些

        也是直接上代码啦~

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define maxn 800000+10#define inf 0x7fffffusing namespace std;int n,m,l,r,op;int ll[maxn],rr[maxn];long long k,a[maxn],w[maxn],tag[maxn];long long read(){ long long xx=0,kk=1;char p=' '; while(!isdigit(p)){p=getchar();if(p=='-')kk=-1;} while(isdigit(p)){xx=xx*10+p-'0';p=getchar();} return kk*xx;}void pushdown(int num){ tag[num<<1]+=tag[num]; tag[num<<1|1]+=tag[num]; w[num<<1]+=tag[num]*(rr[num<<1]-ll[num<<1]+1);//打tag的时候顺便修改w，虽然不知道为什么，但这样做貌似在递归时会方便一点点 w[num<<1|1]+=tag[num]*(rr[num<<1|1]-ll[num<<1|1]+1); tag[num]=0;}void build(int l,int r,int num){ ll[num]=l,rr[num]=r; if(l==r){w[num]=a[l];return;} int mid=(l+r)>>1; build(l,mid,num<<1); build(mid+1,r,num<<1|1); w[num]=w[num<<1]+w[num<<1|1];}void add(int l,int r,int k,int num){ if(ll[num]>r||rr[num]
             
              =l&&rr[num]<=r) { tag[num]+=k; w[num]+=k*(rr[num]-ll[num]+1); return; } pushdown(num);//注意修改时要pushdown标记，因为要靠子节点的w来修改当前节点的w add(l,r,k,num<<1); add(l,r,k,num<<1|1); w[num]=w[num<<1]+w[num<<1|1];}long long query(int l,int r,int num){ if(ll[num]>r||rr[num]
              
               =l&&rr[num]<=r)return w[num]; pushdown(num); return query(l,r,num<<1)+query(l,r,num<<1|1);}int main(){ n=read();m=read(); for(int i=1;i<=n;++i)a[i]=read(); build(1,n,1); for(int j=1;j<=m;++j) { op=read();l=read();r=read(); switch(op) { case 1:{k=read();add(l,r,k,1);break;} case 2:{printf("%lld\n",query(l,r,1));break;} } } return 0;}

 

 
   
3.权值线段树
 
   
         听说是个黑科技，貌似能代替treap和splay的弱者福音？？（但蒟蒻我还是打不来
 
   
4.带旋treap
 
   
         虽说是省选内容但是现在noip基本都有涉及，为了达成万水水的要求当然还是要熟练掌握。
 
   
         一开始是照着石学姐的代码码的，懵逼中把模板题水了过去。现在回过头来好好理解了一下代码，加入了一些自己的理解（还是自己码的代码看起来舒服qvq）打算能像xio姐一样十分钟一个板子
 
   
          自己的理解都在注释中啦，感觉还是比较清晰吧qvq
 
   
 
    
#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define ll long long#define maxn 200000+5#define inf 0x7fffffffusing namespace std;int opt,n,x,tot,root;int son[maxn][2],rnd[maxn],cnt[maxn],val[maxn],sz[maxn];int read(){ int xx=0,kk=1;char p=' '; while(!isdigit(p)){p=getchar();if(p=='-')kk=-1;} while(isdigit(p)){xx=xx*10+p-'0';p=getchar();} return xx*kk;}void update(int pos){ sz[pos]=sz[son[pos][0]]+sz[son[pos][1]]+cnt[pos];//sz是该节点及其下面子节点的数的个数之和，cnt是等于当前节点的值的数的个数 }void rotate(int &pos,int p)//p为1时左旋（将右儿子转到父节点），p为0时右旋（将左儿子转到父节点） { int s=son[pos][p]; sz[s]=sz[pos]; son[pos][p]=son[s][p^1]; son[s][p^1]=pos; update(pos); pos=s;} void insert(int &pos,int x){ if(!pos) { pos=++tot; val[pos]=x;//val使treap维持二叉树的性质（权值 右>中>左 rnd[pos]=rand();//rnd使treap维持堆的性质（使树深度尽可能变成logn } sz[pos]++; if(val[pos]==x){cnt[pos]++;return;} int p=x>val[pos]; insert(son[pos][p],x); if(rnd[son[pos][p]]
            
             1){sz[pos]--;cnt[pos]--;return;} if(!(sz[son[pos][0]]*sz[son[pos][1]])){pos=son[pos][0]+son[pos][1];return;} int p=rnd[son[pos][0]]>rnd[son[pos][1]];//将左右儿子中优先级小的转到父节点 rotate(pos,p);sz[pos]--; del(son[pos][p^1],x); } else{sz[pos]--;del(son[pos][x>val[pos]],x);}}int qrank(int pos,int x){ if(val[pos]==x)return sz[son[pos][0]]+1; if(x
             
              sz[son[pos][0]]&&x<=sz[son[pos][0]]+cnt[pos])return val[pos];//也可以写成x<=sz[pos]-sz[son[pos][1]]; if(x<=sz[son[pos][0]])return qnum(son[pos][0],x); return qnum(son[pos][1],x-sz[son[pos][0]]-cnt[pos]); }int qpre(int pos,int x){ if(!pos)return -inf; if(x>val[pos])return max(val[pos],qpre(son[pos][1],x));//将符合不大于x的数都进行比较，最大值就是前驱前驱 else return qpre(son[pos][0],x); }int qnxt(int pos,int x){ if(!pos)return inf; if(x
             
            
           
          
         
        
       
      
     
 
   
 
   
 
 
   
5.无旋treap
 
   
         貌似和带旋的差不多，为了巩固treap应该还是会找个时间学学的qwq
 
   
6.splay
 
   
         splay更是懵中带懵，跟着大佬的代码码了几遍，有点点自己的理解了，但要自己实现目前还有点点困难qwq
 
   
         要注意的是一颗splay很难同时实现翻转的插入，删除操作的。因为进行翻转操作时是打的tag并没有真正的翻转，只有在输出的时候才下放标记，下放标记的同时又破坏了二叉树的性质。但听机房大佬说貌似可以存个时间点，然后进行一些骚操作（太强啦！），反正我是不会啦！
 
   
        splay中很多小细节很容易写炸，需要多加练习
 
   
 
    
#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define maxn 100000+10using namespace std;int n,m,l,r,root,tot;int son[maxn][2],sz[maxn],fa[maxn],w[maxn],mark[maxn];int read(){ int xx=0,kk=1;char p=' '; while(!isdigit(p)){p=getchar();if(p=='-') kk=-1;} while(isdigit(p)){xx=xx*10+p-'0';p=getchar();} return kk*xx;}void init(int n,int x,int f){ sz[n]=1,w[n]=x,fa[n]=f;}void pushup(int x){ sz[x]=sz[son[x][0]]+sz[son[x][1]]+1;//由于模板题中没有重复元素，所以直接+1就ok了，如果重复的话此处把1改为cnt[x] }void pushdown(int x){ if(!mark[x])return; mark[son[x][0]]^=1; mark[son[x][1]]^=1; mark[x]=0; swap(son[x][0],son[x][1]);//交换左右儿子的下标 }void rotate(int x)//注意赋值顺序！！ { int pre=fa[x],ppre=fa[pre]; int pos=son[pre][1]==x; int ppos=son[ppre][1]==pre; son[ppre][ppos]=x;fa[x]=ppre; son[pre][pos]=son[x][pos^1]; fa[son[x][pos^1]]=pre; son[x][pos^1]=pre;fa[pre]=x;//这句话应该放在最后面，因为会影响前面的赋值操作 pushup(pre);pushup(x);}void splay(int x,int goal){ while(fa[x]!=goal) { int pre=fa[x],ppre=fa[pre]; if(ppre!=goal) son[ppre][1]==pre^son[pre][1]==x?rotate(x):rotate(pre);//该节点机器父节点都为左节点或右节点时先转父节点再转该节点，不知道为什么==，可能是为了保持平衡吧ww rotate(x); } if(!goal) root=x;}void insert(int x){ int u=root,pre=0; while(u) pre=u,u=son[u][x>w[u]]; u=++tot; if(pre)son[pre][x>w[pre]]=u; init(u,x,pre); splay(u,0);}int rank(int x){ int u=root; while(1) { pushdown(u); if(sz[son[u][0]]>=x)u=son[u][0]; else if(sz[son[u][0]]+1==x)return u; else x-=sz[son[u][0]]+1,u=son[u][1]; }}void work(int l,int r){ l=rank(l);r=rank(r+2); splay(l,0);splay(r,l); mark[son[son[root][1]][0]]^=1;//在大于l小于r+2的节点上打标记，最后输出结果时要-1 }void print(int u){ pushdown(u); if(son[u][0]) print(son[u][0]); if(w[u]>1&&w[u]
           
          
         
        
       
      
     
 
   
 
   
 
 
   
7.主席树
 
   
           主席树貌似是提高组考点来着orz...然而弱爆了的南瓜现在才会打板子呜呜呜
 
   
           目前了解到的主席树的作用一共就两个吧（学艺不精QAQ）
 
   
        1.区间k大值
 
   
                     考虑离散化，按权值从小到大进行插入操作，然后对于一个查询r到l的k大值，我们只需要将第r颗树减去第l颗树，就可以得到在原来每个区间中有多少个数，在树上跑一遍第k个数的位置，再把值输出来就好啦（主要是有一个离散化后的数组和原来的数组说起来会有点点绕orz，由于南瓜语言表达能力实在是太弱啦，就感性理解一下下吧qwq
 
   
 
    
#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define maxn 200010<<5#define debug(x) cout<<#x<<" = "<
            
             <
             
              >1; build(son[num][0],l,mid); build(son[num][1],mid+1,r);}int add(int pre,int l,int r){ int now=++cnt;sum[now]=sum[pre]+1; son[now][0]=son[pre][0],son[now][1]=son[pre][1]; if(l==r) return now; int mid=(l+r)>>1; if(pos<=mid) son[now][0]=add(son[now][0],l,mid); else son[now][1]=add(son[now][1],mid+1,r); return now;}int query(int x,int y,int l,int r,int k){ if(l==r) return b[l]; int mid=(l+r)>>1,del=sum[son[x][0]]-sum[son[y][0]]; if(del>=k) return query(son[x][0],son[y][0],l,mid,k); return query(son[x][1],son[y][1],mid+1,r,k-del);}int main(){ n=read(),m=read(); for(int i=1;i<=n;++i) b[i]=a[i]=read(); sort(b+1,b+1+n); end=unique(b+1,b+1+n)-b-1; build(root[0],1,end); for(int i=1;i<=n;++i) { pos=lower_bound(b+1,b+end+1,a[i])-b; root[i]=add(root[i-1],1,end); } for(int i=1;i<=m;++i) { l=read(),r=read(),k=read(); printf("%d\n",query(root[r],root[l-1],1,end,k)); } return 0;}
             
            
           
          
         
        
       
      
     
 
   
 
   
 
 
   
        2.求t时刻的值
 
   
                     这个很好理解啦，比没有前一个那么绕orz，就直接上代码啦
 
   
 
    
#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define maxn 1000005<<5#define debug(x) cout<<#x<<" = "<
            
             <
             
              >1; build(son[now][0],l,mid); build(son[now][1],mid+1,r);}void add(int &now,int pre,int l,int r,int pos,int val){ now=++cnt;w[now]=w[pre]; son[now][0]=son[pre][0],son[now][1]=son[pre][1]; if(l==r){w[now]=val;return;} int mid=(l+r)>>1; if(mid>=pos) add(son[now][0],son[pre][0],l,mid,pos,val); else add(son[now][1],son[pre][1],mid+1,r,pos,val);}int query(int now,int l,int r,int pos){ if(l==r) return w[now]; int mid=(l+r)>>1; if(mid>=pos) return query(son[now][0],l,mid,pos); else return query(son[now][1],mid+1,r,pos);}int main(){ n=read(),m=read(); for(int i=1;i<=n;++i) a[i]=read(); build(root[0],1,n); for(int i=1;i<=m;++i) { tim=read(),opt=read(),pos=read(); switch(opt) { case 1:{val=read();add(root[i],root[tim],1,n,pos,val);break;} case 2:{printf("%d\n",query(root[tim],1,n,pos));root[i]=root[tim];break;} } } return 0; }
             
            
           
          
         
        
       
      
     
 
   
 
   
 
 
   
        然后后排提示一下，主席树的空间非常炸，一般开到nlogn（一般是开2^5倍叭？！）就收手啦，小了会re，大了会mle，不仅如此，大常数选手南瓜还疯狂在tle的边缘试探qwq
 
   
                  
 
   
8.LCT
 
   
 
 
   
最后这个由于我太菜啦，所以连干什么的都不知道QAQ
 
   
 
 
   
果然还是太弱啦！还要加油哦qvq
 
   
 
 
   
To Be Continued...
 
  
 
  
转载于:https://www.cnblogs.com/pumpkin-qwq/p/9551339.html
 

        

        

            你可能感兴趣的文章
        

        
            

                
关于JavaScript词法

                
查看>>

            

        
            

                
FreeSwitch中的会议功能（4）

                
查看>>

            

        
            

                
MySQL中创建用户分配权限（到指定数据库或者指定数据库表中）

                
查看>>

            

        
            

                
php函数总结

                
查看>>

            

        
            

                
Java 对象的封装，继承，抽象，接口写法

                
查看>>

            

        
            

                
Java抽象类与接口的区别

                
查看>>

            

        
            

                
换教室

                
查看>>

            

        
            

                
Oracle笔记（4）：一个存储过程编写及C#调用

                
查看>>

            

        
            

                
第二轮冲次会议第二次

                
查看>>

            

        
            

                
【转】Erlang代码片段

                
查看>>

            

        
            

                
BZOJ 3434 [Wc2014]时空穿梭

                
查看>>

            

        
            

                
typescript+react+antd基础环境搭建

                
查看>>

            

        
            

                
好用的meta标签

                
查看>>

            

        
            

                
Webpack从入门到上线

                
查看>>

            

        
            

                
poj1987 Distance Statistics

                
查看>>

            

        
            

                
接口、性能测试交流群

                
查看>>

            

        
            

                
ArcCore重构-头文件引用问题的初步解决

                
查看>>

            

        
            

                
Rocket - config - implicit Parameters

                
查看>>

            

        
            

                
eclipse中的tomcat中修改部署项目的路径

                
查看>>

            

        
            

                
软件工程概论作业一

                
查看>>

            

        
    






    

            

                
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

                

                    当前时间: 2025-01-06 14:28:49  
                    当前IP: 18.116.49.143  
                    联系邮箱:javaeecc@qq.com
                        Copyright © 2020 - 2022 baihongyu.com
                    京ICP备2021015314号-2
                

            


                
                    

                    强烈建议你试试无所不能的CHAT-GPT，快点击我
                    

                
                
                    

                        强烈建议你试试无所不能的CHAT-GPT，快点击我