首页 > 其他分享 >后缀平衡树

后缀平衡树

时间:2022-12-26 22:00:23浏览次数:35  
标签:return 后缀 tree son int lson 平衡

继续搞点字符串。后缀平衡树。

后缀平衡树,就是后缀数组上平衡树。它的中序遍历是后缀数组。

但是它可以在线 \(O(n\log n)\) 构建,虽然码量大点。

当然你可以先把后缀数组求出来再建平衡树,但是这就没意义了。

显然我们每次插入删除字符的时候一定要在整个串最前面插入删除。也就是维护一大堆后缀。平衡树的每个节点就是一个后缀。

每次插入删除的复杂度平静在于比较两个后缀的大小。暴力比较是T飞的。观察到一个性质(以插入为例):新插入的后缀一定是形如 \(cS\) (\(c\) 是字符,\(S\) 是在平衡树里的一个后缀)。那么可以直接比较第一个字符,如果不同直接出。如果相同,就可以比较剩下的后缀,这个可以通过给每个后缀赋值代表大小关系来做到。

下面是一份基于替罪羊树实现的板子。板子很简单,查一个字符只要查有多少小于等于的后缀和小于的后缀减一下就行了。顺带一提后缀平衡树只要平衡树可持久化那它就可持久化。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson tree[x].son[0]
#define rson tree[x].son[1]
using namespace std;
const double mx=1e16;
int n,m;
char s[2000010],str[2000010];
struct node{
    int son[2],size;
    double tag;
}tree[2000010];
int rt,a[2000010];
bool cmp(int x,int y){
    return s[x]<s[y]||(s[x]==s[y]&&tree[x-1].tag<tree[y-1].tag);
}
void pushup(int x){
    tree[x].size=tree[lson].size+tree[rson].size+1;
}
void dfs(int x){
    if(!x)return;
    dfs(lson);
    a[++a[0]]=x;
    dfs(rson);
    lson=rson=0;
}
void build(int &x,int L,int R,double l,double r){
    if(L>R)return;
    int mid=(L+R)>>1;
    double Mid=(l+r)/2;
    x=a[mid];tree[x].tag=Mid;
    build(lson,L,mid-1,l,Mid);
    build(rson,mid+1,R,Mid,r);
    pushup(x);
}
bool judge(int x){
    return 1.0*max(tree[lson].size,tree[rson].size)>0.7*tree[x].size;
}
void found(int &x,double l,double r){
    a[0]=0;
    dfs(x);
    build(x,1,a[0],l,r);
}
void ins(int &x,int pos,double l,double r){
    if(!x){
        x=pos;tree[x].size=1;
        tree[x].tag=(l+r)/2;
        lson=rson=0;
        return;
    }
    if(cmp(pos,x))ins(lson,pos,l,tree[x].tag);
    else ins(rson,pos,tree[x].tag,r);
    pushup(x);
    if(judge(x))found(x,l,r);
}
void del(int &x,int pos){
    if(x==pos){
        if(!lson||!rson)x=lson|rson;
        else{
            int y=lson,tmp=x;
            while(tree[y].son[1]){
                tmp=y;
                tree[tmp].size--;
                y=tree[y].son[1];
            }
            if(tmp==x){
                tree[y].son[1]=tree[x].son[1];
                x=y;
                pushup(x);
            }
            else{
                tree[y].son[0]=tree[x].son[0];
                tree[y].son[1]=tree[x].son[1];
                tree[tmp].son[1]=0;
                x=y;
                pushup(x);
            }
        }
        return;
    }
    if(cmp(pos,x))del(lson,pos);
    else del(rson,pos);
    pushup(x);
}
bool com(int x){
    for(int p=1;str[p];p++,x=(x?x-1:0)){
        if(str[p]<s[x])return true;
        else if(str[p]>s[x])return false;
    }
    return false;
}
int query(int x){
    if(!x)return 0;
    if(com(x))return query(lson);
    else return tree[lson].size+1+query(rson);
}
void decode(char s[],int mask){
    int len=strlen(s);
    for(int i=0;i<len;i++){
        mask=(mask*131+i)%len;
        swap(s[i],s[mask]);
    }
}
int mask,ans;
int main(){
    scanf("%d%s",&m,s+1);n=strlen(s+1);
    for(int i=1;i<=n;i++)ins(rt,i,0,mx);
    while(m--){
        char od[10];scanf("%s",od);
        if(od[0]=='A'){
            scanf("%s",str+1);
            decode(str+1,mask);
            int len=strlen(str+1);
            for(int j=1;j<=len;j++){
                s[n+j]=str[j];ins(rt,n+j,0,mx);
            }
            n+=len;
        }
        else if(od[0]=='Q'){
            scanf("%s",str+1);
            decode(str+1,mask);
            int len=strlen(str+1);
            reverse(str+1,str+len+1);
            str[len+1]='Z'+1;str[len+2]=0;
            ans=query(rt);
            str[len]--;
            ans-=query(rt);
            printf("%d\n",ans);
            mask^=ans;
        }
        else{
            int k;scanf("%d",&k);
            for(int j=n;j>n-k;j--)del(rt,j);
            n-=k;
        }
    }
    return 0;
}

应用不知道。

标签:return,后缀,tree,son,int,lson,平衡
From: https://www.cnblogs.com/gtm1514/p/17007015.html

相关文章

  • php获取文件后缀的方法
    本文实例为大家分享了9种php获取文件后缀的方法,供大家参考,具体内容如下<?php/***CreatedbyPhpStorm.*User:liuft*Date:2016/3/7*Time:15:46*///第......
  • 平衡树
    fhq-treap对于一个集合,需要维护它,我们考虑一个包含集合中所有元素的有序序列,并使用一棵树,其中每一个子树都对应着一个子序列:这棵树有什么性质呢?首先它是一棵二叉查找树,......
  • 平衡树
    平衡树包括很多种类,常见的有B树、AVL树、红黑树等。这些树都大致平衡,能保证最坏情况下为O(logN)的性能,因此广受大家的欢迎。但是由于平衡机制的不同,这些树都有着不同的应......
  • P3369普通平衡树 学习笔记
    题意写一棵平衡树,需要实现如下几种操作:插入\(x\)数删除\(x\)数(若有多个相同的数,因只删除一个)查询\(x\)数的排名(排名定义为比当前数小的数的个数\(+1\))查......
  • 嘤嘤的新平衡树
    给定一棵二叉树,二叉树的每个结点只有0或2个孩子。你需要对每个结点赋值一个正整数,使得每个结点的左右子树权值和相等。你需要返回所有结点的最小权值和对109+7取模的结......
  • #yyds干货盘点# LeetCode程序员面试金典:检查平衡性
    题目:实现一个函数,检查二叉树是否平衡。在这个问题中,平衡树的定义如下:任意一个节点,其两棵子树的高度差不超过1。示例1:给定二叉树[3,9,20,null,null,15,7]  3 /\......
  • R语言统计学DOE实验设计:用平衡不完全区组设计(BIBD)分析纸飞机飞行时间实验数据
    全文链接:http://tecdat.cn/?p=31010原文出处:拓端数据部落公众号平衡不完全区组设计(BIBD)是一个很好的研究实验设计,具有从统计的角度看各种所需的特征。最近我们被要求撰......
  • P3369 【模板】普通平衡树
    题目链接题目要求:插入数据,删除数据,查询数的排名,查询排名为x的数,找前驱,找后继旋转操作,左旋和右旋,旋转$x$,旋转操作一定要符合先序遍历前后一致voidrotate(intx){ ......
  • 广义后缀自动机
    广义SAM。这玩意和SAM的关系就类似AC自动机和kmp的关系,也就是可以处理多个串之间的问题。就像AC自动机是kmp在trie上的拓展,广义SAM也是SAM在trie上的拓......
  • 后缀自动机,SAM
    后缀自动机,SAM。这玩意可以解决一群字符串问题,但是它本身的原理相当复杂,因此理解这玩意比较困难(10级考点)。以下基本没有证明。定义SAM可以在线性的空间和时间复杂度内......