嵌套结构（树套树）学习笔记

Ink_Render · 2021-02-10 10:08:47 · 个人记录

一、引入

说到“嵌套”，大家想的应该都是这样：

{ ( ) }

即一层套着一层的模式。那么什么是嵌套结构呢?

在 NOIP 考试范围中，我们需要学习很多数据结构，简单的比如数组，邻接表，较复杂的比如各种树形结构或可持久化结构。但一种数据结构所能解决的问题往往只有为数不多的几种并且是有局限性的。为了让数据结构 B 能够实现更多的操作或是消除其某些方面的问题，我们需要用另一个数据结构 A 来维护多个数据结构 B 之间的关系，这就是嵌套结构。我们常把上面的情况称之为“ A 套 B ”。

二、基本介绍

一个小小的声明：文中的 A ，B ，除特殊情况外，所指均为“ A 套 B ”中的 A ，B 。

嵌套结构有很多种，几乎所有的数据结构都可以相互套。有很多二维数据结构，其实就是“ A 套 A ”的形式的嵌套结构。

在嵌套结构中，看似是用两个数据结构来维护，但实际上，A 与 B 的作用并不相同。本质上来说，嵌套结构其实是由许多的数据结构 B 构成的。在外层的 A ，它的每一个结点都对应着一个数据结构 B ，所以在实际使用中， A 的作用主要是定位，确定需要操作的是哪几个数据结构 B ，而 B 才是真正记录信息的。

或许这种介绍不太直观，给大家举一个很简单的例子：

现在有一个数组套数组（即二维数组）,每一个 A 结点对应的一行都是一个一维数组，而整个 A 数组又有四个元素，即一共有四个一维数组，十六个元素。当我们进行修改/查询时，先通过 A 数组确定在哪个 B 数组中，再在 B 数组中进行修改。

例：（假设此数组名为 p ）查询 p[2][3] 的值时，我们先找到 p[2] 即 A2 ，再找到这个一维数组的第三个，最终答案为 1 。

三、代码实现

由于嵌套结构的多样性，代码实现部分只分析主要框架。

定义

在初学嵌套结构时，一般建议大家使用结构体双层嵌套的形式，即：

struct A
{
    int b[];//数据结构B
}a[];//数据结构A

但在熟练之后可以转换为一般的二维形式，即直接用 a[][] ，前一维是 A ，后一维是 B 。为了帮助大家更好的理解二维形式，本文中接下来的部分，都会使用二维形式。

修改/查询

加入和查询结构上基本相同，都是需要我们找到符合条件的位置。我们首先在 A 中进行定位，找到需要修改的那些 B ，再对 B 进行修改操作。以下以修改为例：

嵌套形式：

void insert()//修改 B
{

}
void pre_ins()//修改 A
{
    for()
   {
        //找到满足条件的 B
      insert();
   }
}

二维形式：

void insert()
{
    for()//修改 A（找 B）
   {
        for()//修改 B
      {

      }
   }
}

ps：有些嵌套结构是无法使用二维形式的，比如其中有线段树时，需要用递归形式实现。所以除了一些非常简单的嵌套结构，建议大家使用嵌套形式。

四、应用/例题

在引入中我们就说过，嵌套结构一般是为了“让数据结构 B 能够实现更多的操作或是消除其某些方面的问题”。接下来，我们就从这两方面进行分析与实战：

实现更多操作

最经典的就是各种二维数据结构，在这里，我们选用两类较为简单的数据结构：树状数组和线段树。

二维树状数组：P4054 [JSOI2009]计数问题
二维线段树：UVA11297 Census

这两个嵌套结构都是将数据结构原来的操作从一个序列（一维）转变到了一个矩阵（二维），从而实现了在矩阵中维护信息。

以下是两题的代码，其中二维树状数组使用的是前文中的二维形式，而线段树使用的是嵌套形式，读者可以将两份代码进行对比分析。

二维树状数组：

#include<bits/stdc++.h>
using namespace std;
const int N=305,C=105;
int n,m,q;
int col[N][N],t[N][N][C];
int lowbit(int x) {return x&(-x);}
void insert(int x,int y,int c)
{
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=m;j+=lowbit(j))
            t[i][j][c]++;       
    return;
}
void erase(int x,int y,int c)
{
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=m;j+=lowbit(j))
            t[i][j][c]--;
    return;
}
int que(int x,int y,int c)
{
    int s=0;
    for(int i=x;i>=1;i-=lowbit(i))
        for(int j=y;j>=1;j-=lowbit(j))
            s+=t[i][j][c];
    return s;
}
int main()
{
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(x=1;x<=n;x++)
        for(y=1;y<=m;y++)
        {
            scanf("%d",&col[x][y]);
            insert(x,y,col[x][y]);
        }
    scanf("%d",&q);
    int op,x2,y2;
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&x,&y,&z);
            erase(x,y,col[x][y]);
            col[x][y]=z;
            insert(x,y,z);
        }
        else
        {
            scanf("%d%d%d%d%d",&x,&x2,&y,&y2,&z);
            int ans=que(x2,y2,z)-que(x2,y-1,z)-que(x-1,y2,z)+que(x-1,y-1,z);
            printf("%d\n",ans);
        }
    }
    return 0;
}

二维线段树

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,q,maxn,minn;
int t[2][N<<2][N<<2];//0 max 1 min
void pushup1(int k,int last)
{
    t[0][last][k]=max(t[0][last][k<<1],t[0][last][k<<1|1]);
    t[1][last][k]=min(t[1][last][k<<1],t[1][last][k<<1|1]);
}
void pushup2(int k,int last)
{
    t[0][last][k]=max(t[0][last<<1][k],t[0][last<<1|1][k]);
    t[1][last][k]=min(t[1][last<<1][k],t[1][last<<1|1][k]);
}
void insert(int k,int l,int r,int last,int x,int w,bool flag)
{
    if(l==r)
    {
        if(flag) t[0][last][k]=t[1][last][k]=w;
        else pushup2(k,last);
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) insert(k<<1,l,mid,last,x,w,flag);
    else insert(k<<1|1,mid+1,r,last,x,w,flag);
    pushup1(k,last);
    return;
}
void pre_ins(int k,int l,int r,int x,int x2,int w)
{
    if(l==r)
    {
        insert(1,1,n,k,x2,w,true);
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) pre_ins(k<<1,l,mid,x,x2,w);
    else pre_ins(k<<1|1,mid+1,r,x,x2,w);
    insert(1,1,n,k,x2,w,false);
    return;
}
void que(int k,int l,int r,int last,int x,int y)
{
    if(x<=l && r<=y)
    {
        maxn=max(maxn,t[0][last][k]);
        minn=min(minn,t[1][last][k]);
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) que(k<<1,l,mid,last,x,y);
    if(y>mid) que(k<<1|1,mid+1,r,last,x,y);
    return;
}
void pre_que(int k,int l,int r,int x,int y,int x2,int y2)
{
    if(x<=l && r<=y)
    {
        que(1,1,n,k,x2,y2);
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) pre_que(k<<1,l,mid,x,y,x2,y2);
    if(y>mid) pre_que(k<<1|1,mid+1,r,x,y,x2,y2);
    return;
}
int main()
{
    memset(t[1],0x7f,sizeof t[1]);
    memset(t[0],0x8f,sizeof t[0]);
    cin>>n;
    int x1,y1,x2,y2,v;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>v;
            pre_ins(1,1,n,i,j,v);
        }
    cin>>q;
    char op;
    for(int i=1;i<=q;i++)
    {
        cin>>op;
        if(op=='c')
        {
            cin>>x1>>y1>>v;
            pre_ins(1,1,n,x1,y1,v);
        }
        if(op=='q')
        {
            maxn=-2e9,minn=2e9;
            cin>>x1>>y1>>x2>>y2;
            pre_que(1,1,n,x1,x2,y1,y2);
            cout<<maxn<<" "<<minn<<endl;
        }
    }
    return 0;
}

消除某些问题

同样也十分经典的问题，动态区间第 k 小（大）。其中包括单点修改和区间修改。

单点修改：P2617 Dynamic Rankings
区间修改：P3332 [ZJOI2013]K大数查询

学过主席树的童鞋应该知道（没学过可以看我的另一篇博客），主席树的模板是静态区间第 k 小，那么如何进行加强使其可以进行修改呢？我们先来考虑主席树无法修改的原因：修改操作

（咕咕咕）

嵌套结构（树套树） 学习笔记

一、引入

二、基本介绍

三、代码实现

四、应用/例题

嵌套结构（树套树）学习笔记