2025广东省集Div2数据结构1

0. 前言

Q1. 要讲什么？

A1. 三棵树：线段树、平衡树、01Trie。无根号状物，请放心食用！！！

Q2. 为什么要讲这么简单的树？

A2. 首先，这三棵树在 noi 大纲中都是属于提高级的内容。

【 6 】线段树

【 6 】字典树（Trie树）

【 8 】平衡树：AVL、treap、splay等

级别更低的算法就意味着更容易被考到，考到所带来的模板差距（这里指一些人不会这个模板导致做不了题）也就越小。所以这些树是比较食用的。

1. 正文

1.1 线段树

~~线段树是普及组内容。~~

普通的线段树和主席树没有什么好讲的，我们讲一点高级技巧。

简单势能线段树

势能线段树就是在线段树上操作会消耗势能。（部分题目中势能也有可能会增加）

势能的总大小是可接受的，因此在线段树上暴力进行一些操作的时间复杂度是正确的。

常见的势能操作有：

$O(n\log V)$ $O(n\log V)$ 。
$\log$ $O(\log V)$ 次的操作。
$\gcd$ $O(\log V)$ $\gcd$ $2$ 。

例题1：洛谷 P4145 上帝造题的七分钟 2 / 花神游历各国
$n$ $[1,V]$ $m$ 次如下两种操作：
$[l,r]$ $a_i\leftarrow \lfloor \sqrt{a_i}\rfloor$ 。
$[l,r]$ 中的数的和。
$n,m\leq 10^5$ $1\leq V\leq 10^{12}$ 。

题解

$\log V$ $1$ $6$ 次），因此能开根号的情况下暴力开根号的操作次数是对的。
$O(n\log n+m\log n\log V)$ 。

例题2：洛谷 P9989 [Ynoi Easy Round 2023] TEST_69
$n$ $[1,V]$ $m$ 次以下操作：
$[l,r]$ $i$ $a_i\leftarrow \gcd(a_i,x)$ $x$ $[1,V]$ 。
$[l,r]$ $2^{32}$ 取模。
$n\leq 2\times 10^5$ $m\leq 5\times 10^5$ $1\leq V\leq 10^{18}$ 。

题解

$\gcd$ $\log V$ $1$ 。
$\text{lcm}$ $\text{lcm}|x$ $x$ $\gcd$ 后值不会发生变化，因此无需递归下去。
$\text{lcm}$ $V+1$ $\min$ 即可。
$O(m\log n\log V)$ 。

1.2 01Trie

Trie 树也都会吧，01Trie 就是值域只有 0 和 1 的 Trie，在大部分情况下比普通的 Trie 有用，因为解决的不是字符串有关的问题，而是二进制位运算有关的问题。

如果想检测一下自己的到底会不会 01Trie，请到这题。

可持久化 01Trie

这个感觉太简单了，有兴趣的自己可以看一看。

原理大概和主席树差不多。

这个是模板题。

我自己都懒得写......

”满子树压缩“ 01Trie

“满子树压缩”这个名字是我自己起的。

$O(\log X)$ $X$ 个连续的数的信息。

$[p2^k,(p+1)2^k-1]$ 这样的区间中的所有信息。

例题：洛谷 P7156 [USACO20DEC] Cowmistry P
$S$ $\leq K$ $10^9+7$ 取模。
$S$ $n$ $[L_i,R_i]$ 并起来得到。
$n\leq 2\times 10^4$ $0\leq K\leq 10^9$ $0\leq L_i\le R_i\leq 10^9$ 。

$K,R_i\leq 10^6$

题解

首先关于这种异或大小限制的题，第一个想法就是把这些数扔到 01Trie 上去。

$0$ $1$ $1$ $0$ 。

那么那两个最高不同位相同的数异或起来一定不是三个数中两两异或的最大值。因此我们只需要考虑与另外两个数最高不同位不同的那个数并同时考虑与其异或起来最大的那个数即可。

$k$ $x'$ $y'$ $k$ $k'$ $\oplus$ 表示按位异或）：

$x'\oplus y'<k'$ $x\oplus y<k$ ，随便取都可以。
$x'\oplus y'>k'$ $x\oplus y>k$ ，怎么取都不合法。
$x'\oplus y'=k$ ，这种情况直接向下递归即可。

$x'$ $k$ $y'$ ，这意味着一条路径所对应的另一条路径是唯一的。因此上述算法的复杂度相当于整棵 01Trie 的大小。

$S$ $10^9$ 个元素，这意味着我们根本不能遍历整棵 01Trie。

$[p2^k,(p+1)2^k-1]$ 的区间，区间内不作拆分，并扔到 01Trie 上。

$x'\oplus y'=k$ 相同，也是可以算出来这两个区间的答案的。

$p$ $q=2^k$ $k$ $k''$ $a\oplus b=c$ $a,b,c$ 中的任意两个时，另外的一个也可以被确定。

$0\leq z\leq k''$ $d$ $0\leq a,b<2^k$ $0\leq a\oplus b<2^k$ $[0,2^k-1]$ $(k''+1)p$ 。

$O(n\log^2 V)$ $V$ 是值域大小。

但是别忘了还有对应的第三个数，其实这个只需要在递归的路径上统计有多少个数异或另一条路径比当前路径异或另一条路径的值小即可。

注意会有两条路径完全一致的情况，这种情况需要特殊处理。

鉴于这题细节比较多，这里给出我的代码。

代码


xxxxxxxxxx
#include<iostream>
using namespace std;
#define int long long
#define mod 1000000007
int n,k;
int calcall0(int siz)
{
    return ((__int128)siz*(siz-1)*(siz-2)/6)%mod;
}
int calcall1(int siz1,int siz2,int at)
{
    int res31=(siz1*(siz1-1)/2)%mod*siz2;
    int res32=(siz2*(siz2-1)/2)%mod*siz1;
    int res4=siz1*siz2%mod*at;
    return (res31+res32+res4)%mod;
}
int vwork1(int pos,int siz,int at)
{
    if(pos==0)
     return calcall1(siz,siz,at);
    if((k>>(pos-1))&1)
    {
        int ans=calcall1(siz/2,siz/2,at)*2;
        ans+=vwork1(pos-1,siz/2,(at+siz)%mod)*2;
        return ans%mod;
    }
    else
     return vwork1(pos-1,siz/2,at)*2%mod;
}
int vwork0(int pos,int siz)
{
    if(pos==0)
     return 0;
    if((k>>(pos-1))&1)
    {
        int ans=calcall0(siz/2)*2;
        ans+=vwork1(pos-1,siz/2,0);
        return ans%mod;
    }
    else
     return vwork0(pos-1,siz/2)*2%mod;
}
class trie
{
    public:
        #define sN 10000010
        int rt,cnt,tr[sN][2],siz[sN],ed[sN];
        trie()
        {
            rt=cnt=1;
        }
        void insert(int pos,int &o,int l,int r,int x,int y)
        {
            if(l>y||r<x)
             return;
            if(!o)
             o=++cnt;
            if(l>=x&&r<=y)
            {
                siz[o]=r-l+1;
                ed[o]=1;
                return;
            }
            int mid=l+r>>1;
            insert(pos-1,tr[o][0],l,mid,x,y);
            insert(pos-1,tr[o][1],mid+1,r,x,y);
            siz[o]=siz[tr[o][0]]+siz[tr[o][1]];
        }
        void insert(int l,int r)
        {
            insert(30,rt,0,(1<<30)-1,l,r);
        }
        int work1(int pos,int o1,int o2,int at)
        {
            if(!o1||!o2)
             return 0;
            if(pos==0)
             return calcall1(siz[o1],siz[o2],at);
            if(ed[o1]&&ed[o2])
             return vwork1(pos,siz[o1],at);
            if(ed[o1])
            {
                tr[o1][0]=++cnt;
                siz[tr[o1][0]]=siz[o1]/2;
                ed[tr[o1][0]]=1;
                tr[o1][1]=++cnt;
                siz[tr[o1][1]]=siz[o1]/2;
                ed[tr[o1][1]]=1;
            }
            if(ed[o2])
            {
                tr[o2][0]=++cnt;
                siz[tr[o2][0]]=siz[o2]/2;
                ed[tr[o2][0]]=1;
                tr[o2][1]=++cnt;
                siz[tr[o2][1]]=siz[o2]/2;
                ed[tr[o2][1]]=1;
            }
            if((k>>(pos-1))&1)
            {
                int ans=0;
                ans+=calcall1(siz[tr[o1][0]],siz[tr[o2][0]],at);
                ans+=calcall1(siz[tr[o1][1]],siz[tr[o2][1]],at);
                ans+=work1(pos-1,tr[o1][0],tr[o2][1],(at+siz[tr[o1][1]]+siz[tr[o2][0]])%mod);
                ans+=work1(pos-1,tr[o1][1],tr[o2][0],(at+siz[tr[o1][0]]+siz[tr[o2][1]])%mod);
                return ans%mod;
            }
            else
            {
                int ans=0;
                ans+=work1(pos-1,tr[o1][0],tr[o2][0],at);
                ans+=work1(pos-1,tr[o1][1],tr[o2][1],at);
                return ans%mod;
            }
        }
        int work0(int pos,int o)
        {
            if(pos==0||!o)
             return 0;
            if(ed[o])
             return vwork0(pos,siz[o]);
            if((k>>(pos-1))&1)
            {
                int ans=0;
                ans+=calcall0(siz[tr[o][0]]);
                ans+=calcall0(siz[tr[o][1]]);
                ans+=work1(pos-1,tr[o][0],tr[o][1],0);
                return ans%mod;
            }
            else
             return (work0(pos-1,tr[o][0])+work0(pos-1,tr[o][1]))%mod;
        }
        int getans()
        {
            return work0(30,rt);
        }
}tr;
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        int l,r;
        cin>>l>>r;
        tr.insert(l,r);
    }
    cout<<tr.getans()<<endl;
}
//一遍过所有样例，我真牛！！！！！！！

1.3 平衡树

介绍

平衡树有很多种，什么 Splay 啊、Treap 啊、黑红树啊。

我认为只要学 FHQ Treap 就够了。无他，简单，好记。

核心操作

$\log n$ 级别。

FHQ Treap 的核心操作有两个：分裂和合并。

按值分裂

$\leq k$ 分裂成两棵 FHQ Treap。

$\texttt{split}(o,k,x,y)$ $o$ $\leq k$ $x$ $y$ $x$ $y$ 由这个函数返回。

$k$ $q$ ：

$q\leq k$ $x$ 树内，递归进右子树子问题。
$q>k$ $y$ 树内，递归进左子树子问题。
$x$ $y$ 树都是空树。

$O(dep)$ $dep$ 是整棵树深度。

按大小分裂

$k$ $k$ $x$ $y$ 树。写法有点类似与线段树上二分。

合并

合并操作就是将两棵 FHQ Treap 合并成一棵 FHQ Treap，但是需要事先保证两棵树之间的权值大小关系，即需要保证左侧树的所有节点的权值均小于右侧树所有节点的权值。

$\texttt{merge}(x,y)$ $x$ $y$ $x$ $y$ 为上文中的右侧树，函数返回这棵合并后的树的根节点。

此时就需要用到上文所说的随机化了，具体的随机化方法是在一开始给每一个点定一个随机权值（不同于上文中的权值，上文的权值是我们手动给定的，这个随机权值是随机得到的），若两个节点在树上为祖先关系，则一定随机权值大的那个是随机权值小的那个的祖先。

$O(\log n)$ 级别的，证明我不会。

$x$ $p$ $y$ $q$ ：

$p>q$ $x$ $x$ $y$ 树进行合并。
$p<q$ $y$ $x$ $y$ 的左子树进行合并。
$x$ $y$ 树中至少有一棵是空树，返回另一棵树即可。

$O(dep)$ 的。

拓展操作

有了上述两个核心操作之后，我们就可以对这棵 FHQ Treap 进行随意“把玩”了。

下列操作绝大部分都是有点“暴力”的，因此会有一点常数，实际上也可以通过非暴力的写法来降低常数，但是写起来会很麻烦。

插入节点

根据新节点的值分裂成两棵树，再按照左-新-右的顺序合并即可。

删除节点

根据要删除节点的值分裂成三棵树，分别是小于该节点，该节点，大于该节点的树，将该节点删除后合并左右两棵树即可。

查询前驱后继

按照查询的值分裂两棵树，根据查的是前驱还是后继来决定是找的是左树的最大值还是右树的最小值，具体可以通过不断在树上走左儿子或者走右儿子来实现。

值查询排名

$x$ 的值分裂出来后统计分裂出来的大小，再将两棵树合并。

$x$ 。

排名查询值

$k-1$ $1$ $n-k$ 分裂成三棵树，查询中间那棵树的节点的权值，然后合并回去。

或者可以手动模拟按大小分裂的流程，但是不实际分裂，找到排名对应的节点。

例题1：洛谷 P6136 【模板】普通平衡树（数据加强版）
$n$ $m$ 次以下若干操作：
$x$ 。
$x$ ，多个只删除一个。
$x$ 在可重集中的排名。
$x$ 位的数。
$x$ 在可重集中的前驱。
$x$ 在可重集中的后继。
$n\leq 10^5$ $m\leq 10^6$ $[0,2^{30}-1]$ 。

题解

平衡树模板题，该讲的上面都已经讲了。可能唯一没讲到是删除怎么只删一个，只需要按值分裂得到中间树之后删除这棵树的根节点，将其两棵子树合并得到新的中间树即可。

这里给出参考代码。

代码


xxxxxxxxxx
#include<iostream>
#include<algorithm>
#include<ctime>
#include<random>
using namespace std;
#define N 2000010
int n,m;
mt19937 rnd(time(0));
class fhq_treap
{
    struct node
    {
        int val,w,sum,ls,rs;
    }tr[N];
    int cnt,rt;
    void upd(int u)
    {
        tr[u].sum=tr[tr[u].ls].sum+tr[tr[u].rs].sum+1;
    }
    void split(int u,int val,int &x,int &y)
    {
        if(u==0)
        {
            x=0;
            y=0;
            return;
        }
        if(tr[u].val<val)
        {
            x=u;
            split(tr[u].rs,val,tr[u].rs,y);
        }
        else
        {
            y=u;
            split(tr[u].ls,val,x,tr[u].ls);
        }
        upd(u);
    }
    int merge(int x,int y)
    {
        if(x==0||y==0)
         return x+y;
        if(tr[x].w>tr[y].w)
        {
            tr[x].rs=merge(tr[x].rs,y);
            upd(x);
            return x;
        }
        else
        {
            tr[y].ls=merge(x,tr[y].ls);
            upd(y);
            return y;
        }
    }
    public:
        void insert(int val)
        {
            int x,y;
            split(rt,val,x,y);
            int u=++cnt;
            tr[u].val=val;
            tr[u].sum=1;
            tr[u].w=rnd()%1000000007;
            rt=merge(x,merge(u,y));
        }
        void del(int val)
        {
            int x,y,z;
            split(rt,val,x,y);
            split(y,val+1,y,z);
            if(y!=0)
             y=merge(tr[y].ls,tr[y].rs);
            rt=merge(x,merge(y,z));
        }
        int getrnk(int val)
        {
            int x,y;
            split(rt,val,x,y);
            int ans=tr[x].sum+1;
            rt=merge(x,y);
            return ans;
        }
        int getval(int rnk)
        {
            int u=rt;
            while(1)
            {
                if(tr[tr[u].ls].sum+1==rnk)
                 break;
                if(tr[tr[u].ls].sum+1>rnk)
                {
                    u=tr[u].ls;
                }
                else
                {
                    rnk-=tr[tr[u].ls].sum+1;
                    u=tr[u].rs;
                }
            }
            return tr[u].val;
        }
        int getfrt(int val)
        {
            int x,y;
            split(rt,val,x,y);
            int u=x;
            while(tr[u].rs!=0)
            {
                u=tr[u].rs;
            }
            rt=merge(x,y);
            return tr[u].val;
        }
        int getnxt(int val)
        {
            int x,y;
            split(rt,val+1,x,y);
            int u=y;
            while(tr[u].ls!=0)
            {
                u=tr[u].ls;
            }
            rt=merge(x,y);
            return tr[u].val;
        }
}fhq;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        fhq.insert(x);
    }
    int las=0,ans;
    for(int i=1;i<=m;i++)
    {
        int opt,x;
        cin>>opt>>x;
        x^=las;
        if(opt==1)
         fhq.insert(x);
        if(opt==2)
         fhq.del(x);
        if(opt==3)
         las=fhq.getrnk(x);
        if(opt==4)
         las=fhq.getval(x);
        if(opt==5)
         las=fhq.getfrt(x);
        if(opt==6)
         las=fhq.getnxt(x);
        if(opt>=3)
         ans^=las;
    }
    cout<<ans<<endl;
}

带 tag 的平衡树

平衡树上 tag 其实非常简单，跟线段树上 tag 差不多的思想，只需要在分裂和合并两个操作遍历到对应节点的时候下传 tag 即可，如果你自己写了额外遍历树的 dfs，记得在那里也加上下传 tag。

基本上，线段树上能放什么 tag，平衡树上就能放什么 tag。

例题2：洛谷 P3391 【模板】文艺平衡树
$n$ $m$ 次以下操作：
$[L_i,R_i]$ 。
$m$ 次变换完后的有序序列。
$n,m\leq 10^5$ $1\leq L_i\leq R_i\leq n$ 。

题解

平衡树 tag 非常经典的一个运用，本题中平衡树的 tag 为该区间是否要翻转。

因为一个区间翻转两次等于没翻转，所以 tag 的状态只有 0 和 1 两种。

怎么对某一个区间打翻转标记呢？将该区间分裂出来并在其根节点打上翻转 tag，最后合并回去即可。

由于是模板题，同样给出参考代码。

代码


xxxxxxxxxx
#include<iostream>
#include<algorithm>
#include<ctime>
#include<random>
using namespace std;
#define N 2000010
int n,m;
mt19937 rnd(time(0));
class fhq_treap
{
    struct node
    {
        int val,w,sum,ls,rs,tag;
    }tr[N];
    int cnt,rt;
    void down(int u)
    {
        if(!tr[u].tag)
         return;
        swap(tr[u].ls,tr[u].rs);
        tr[u].tag=0;
        tr[tr[u].ls].tag^=1;
        tr[tr[u].rs].tag^=1;
    }
    void upd(int u)
    {
        tr[u].sum=tr[tr[u].ls].sum+tr[tr[u].rs].sum+1;
    }
    void split(int u,int siz,int &x,int &y)
    {
        if(u==0)
        {
            x=0;
            y=0;
            return;
        }
        down(u);
        if(tr[tr[u].ls].sum<siz)
        {
            x=u;
            split(tr[u].rs,siz-tr[tr[u].ls].sum-1,tr[u].rs,y);
        }
        else
        {
            y=u;
            split(tr[u].ls,siz,x,tr[u].ls);
        }
        upd(u);
    }
    int merge(int x,int y)
    {
        if(x==0||y==0)
         return x+y;
        if(tr[x].w>tr[y].w)
        {
            down(x);
            tr[x].rs=merge(tr[x].rs,y);
            upd(x);
            return x;
        }
        else
        {
            down(y);
            tr[y].ls=merge(x,tr[y].ls);
            upd(y);
            return y;
        }
    }
    public:
        void insert(int val)
        {
            int x,y;
            split(rt,val,x,y);
            int u=++cnt;
            tr[u].val=val;
            tr[u].sum=1;
            tr[u].w=rnd()%1000000007;
            rt=merge(x,merge(u,y));
        }
        void rotate(int l,int r)
        {
            int x,y,z;
            split(rt,l-1,x,y);
            split(y,r-l+1,y,z);
            tr[y].tag^=1;
            rt=merge(x,merge(y,z));
        }
        void output(int u)
        {
            if(u==0)
             return;
            down(u);
            output(tr[u].ls);
            cout<<tr[u].val<<" ";
            output(tr[u].rs);
        }
        void getans()
        {
            output(rt);
        }
}fhq;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fhq.insert(i);
    }
    int las=0,ans;
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        fhq.rotate(l,r);
    }
    fhq.getans();
}

可持久化平衡树

这个东西没什么用的，也不难，按照线段树照葫芦画瓢即可。

感兴趣的可以自行取洛谷上找模板题。

平衡树有交合并

之前提到平衡树的合并操作都是要求两棵树值域不交的。

那么当遇到两棵树值域有交的情况该如何合并呢？

$O(n\log n)$ 级别。

这里给出一个很简单并且复杂度正确的平衡树合并：将两棵树分别划分成尽量少的若干段，使得这若干段分别没有交，再按照大小顺序逐一进行无交合并即可。

$\log$ 的。

例题3：洛谷 P10284 [USACO24OPEN] Splitting Haybales P
$x$ $n$ $i$ 次操作为：
$x\leq 0$ $x\leftarrow x+a_i$ $x\leftarrow x-a_i$ 。
$q$ $x$ $x$ $L_i$ $R_i$ $x$ 的值。
$n,q\leq 2\times 10^5$ $1\leq a_i\leq 10^5$ $|x|\leq 10^9$ $1\leq L_i\leq R_i\leq n$ 。

题解

$x$ $x$ 现在的值是什么。
$\leq 0$ $>0$ $k$ ，最后再将两棵树合并到一起。
$k$ 可以用平衡树上 tag 实现，由于整体加之后两棵树可能会有重叠，因此我们需要平衡树有交合并。
并没有什么很难的地方，因此这里只给出平衡树有交合并部分的实现。
代码
x
int Merge(int x,int y)
{
    if(x==0||y==0)
     return x+y;
    pushdown(x);
    pushdown(y);
    int md;
    split(y,tr[x].mi,md,y);
    return merge(md,Merge(y,x));
}
$tr[x].mi$ $x$ $\texttt{merge}$ 为核心操作中的平衡树无交合并。

平衡树合并练习：洛谷 P8264 [Ynoi Easy Round 2020] TEST_100

平衡树综合练习：洛谷 P3274 [SCOI2011] 植物大战僵尸