「黑历史」浅谈权值线段树到主席树

Aleph1022

2018-08-03 13:56:12

算法·理论

线段树这种玩意儿，是一种比较基础的数据结构，若是没有理解或是不了解的的请出门左转往期日报：#4 [皎月半洒花] 浅谈线段树（Segment Tree）

有勇气继续看的泥萌都掌握了吧

有言在先：我的码风可能有点迥异，请见谅……

权值线段树和线段树，唯一的本质的区别就是他们维护的东西不一样，因此权值线段树可以查询全局第k大，最小差等线段树无法维护的东西。

权值线段树一般支持以下三个操作：

insert
erase/remove
query

insert操作，其实主要思路就是递归找到新加入的权值对应的结点，然后进行更新该节点的信息。

void insert(int k,int root = 1)
{
    if(seg[root].l == seg[root].r)
    {
        //Update the information
        return ;
    }
    int mid = seg[root].l + seg[root].r >> 1;
    if(k <= mid)//在左儿子当中
        insert(k,lson);
    if(k > mid)//在右儿子当中
        insert(k,rson);
    //Push up the information
}

remove操作，其实也就是把权值对应的结点的信息恢复到insert之前，代码与insert异曲同工。

void remove(int k,int root = 1)
{
    if(seg[root].l == seg[root].r)
    {
        //Remove the information
        return ;
    }
    int mid = seg[root].l + seg[root].r >> 1;
    if(k <= mid)//在左儿子当中
        remove(k,lson);
    if(k > mid)//在右儿子当中
        remove(k,rson);
    //Push up the information
}

其实并没有什么区别（雾）

query操作，对于不同的询问有不同的写法，主要思路和线段树差不多。有时候只是查询整个数列的答案的话就可以直接输出根节点维护的信息。

经典操作：查询k小值。

我们可以让每个结点维护自己区间内出现了多少个数，然后从根节点开始找，每次判断k是否\ \leq\ 左儿子区间的数字个数，如果\ \leq\ ，说明要找的这个数在左儿子区间中，否则在右儿子区间中。

然后以此类推，继续递归找下去。

代码：

int query(int k,int root = 1)
{
    if(seg[root].l == seg[root].r)
        return seg[root].l;//找到了
    int mid = seg[lson].tot;//左儿子区间的数字个数
    if(k <= mid)
        return query(k,lson);//左儿子里面找
    else if(k > mid)
        return query(k - mid,rson);//右儿子里面找
}

这个查询的代码要好好理解，下面不会再讲。

此外，权值线段树再加上可持久化就是我们hjt大佬的主席树，就可以通过历史版本查询区间第k大等等（即把问题扩展到区间）。

那么，我们引入一道例题：

Weight Tarot 权值塔罗牌

Description 题目描述

最近小L收集了一套塔罗牌，每个塔罗牌上面有一个权值，不超过10^5，现有N个操作，分别有以下三种情况：

Add x 如果当前的手牌中没有权值为x的塔罗牌则加入，否则忽略该操作。
Remove x 如果当前的手牌中有权值为x的塔罗牌则弃掉该牌，否则忽略该操作。
Query 查询当前手牌中权值最接近的两张牌的权值之差，如果当前手牌数量少于2张牌，输出-1。

Input Format 输入格式

第一行，一个整数N。

接下来N，每行一个操作。

Output Format 输出格式

对于每个Query操作，输出一行，表示操作的结果。

Sample 样例

Sample Input 样例输入

12
Add 1
Remove 2
Add 1
Query
Add 7
Query
Add 10
Query
Add 5
Query
Remove 7
Query

Sample Output 样例输出

Data Constraint 数据范围

N \leq 10^5

Source 来源

改编自学校OJ一题

Analysis 分析

注意，对于各个操作的描述，可以看出塔罗牌的权值不能重复！

那么，就可以构造一棵根节点区间为[1,10^5]的线段树，~~在树上乱搞，~~这就是权值线段树的核心思想——（划重点）以数据范围为区间进行答案的维护（这句话是自己说的说错了别打我（逃）

大概是这样的：

对于每个结点，我们维护三个值：min,max,diff，分别代表区间最小值，区间最大值，区间最小差。

递归维护的时候，

min=min\{lson.min,rson.min\},max=max\{lson.max,rson.max\}

这个不难理解，但是最小差呢……

思考一下，容易发现更新的时候有三种状态：

左儿子[l,mid]区间维护的最小差
右儿子[mid + 1,r]区间维护的最小差
右儿子区间维护的最小值与左儿子区间维护的最大值的差

然后对于三种情况，min一下就可以了（注意左儿子和右儿子都可能没有数，这时就需要去除对应的情况）

一个技巧：建树的时候可以把最小值初始化为正无穷，把最大值初始化为负无穷，这样更新最小差的时候只需要对第三种状态判断左右最值是否为无穷即可，因为对无穷作min是无用的。

参考代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson (root << 1)
#define rson (lson | 1)
using namespace std;
int n,x;
char opt[15];
struct node
{
    int l,r;
    int max,min,diff;
} seg[400010];
void build(int l,int r,int root = 1)//初始建树操作
{
    seg[root].min = seg[root].diff = 0x3f3f3f3f;
    seg[root].max = -0x3f3f3f3f;
    seg[root].l = l,seg[root].r = r;
    //以上初值不多说
    if(l == r)
        return ;
    int mid = l + r >> 1;
    build(l,mid,lson);
    build(mid + 1,r,rson);
}
void generate(int x,int root = 1)//加牌操作
{
    if(seg[root].l == seg[root].r)
    {
        seg[root].max = seg[root].min = x;
        return ;
    }
    int mid = seg[root].l + seg[root].r >> 1;
    if(x <= mid)
        generate(x,lson);
    if(x > mid)
        generate(x,rson);
    seg[root].max = max(seg[lson].max,seg[rson].max);
    seg[root].min = min(seg[lson].min,seg[rson].min);
    if(seg[lson].max == -0x3f3f3f3f || seg[rson].min == 0x3f3f3f3f)
        seg[root].diff = min(seg[lson].diff,seg[rson].diff);
    else
        seg[root].diff = min(seg[rson].min - seg[lson].max,min(seg[lson].diff,seg[rson].diff));
}
void remove(int x,int root = 1)//弃牌操作
{
    if(seg[root].l == seg[root].r)
    {
        seg[root].max = -0x3f3f3f3f;
        seg[root].min = 0x3f3f3f3f;
        return ;
    }
    int mid = seg[root].l + seg[root].r >> 1;
    if(x <= mid) 
        remove(x,lson);
    if(x > mid)
        remove(x,rson);
    seg[root].max = max(seg[lson].max,seg[rson].max);
    seg[root].min = min(seg[lson].min,seg[rson].min);
    if(seg[lson].max == -0x3f3f3f3f || seg[rson].min == 0x3f3f3f3f)
        seg[root].diff = min(seg[lson].diff,seg[rson].diff);
    else
        seg[root].diff = min(seg[rson].min - seg[lson].max,min(seg[lson].diff,seg[rson].diff));
}
int main()
{
    scanf("%d",&n);
    build(1,100000);//数据范围
    while(n--)
    {
        scanf("%s",opt);
        if(!strcmp(opt,"Add"))
        {
            scanf("%d",&x);
            generate(x);
        }
        else if(!strcmp(opt,"Remove"))//else if减少多余的strcmp调用
        {
            scanf("%d",&x);
            remove(x);
        }
        else if(!strcmp(opt,"Query"))
            printf("%d\n",seg[1].diff == 0x3f3f3f3f ? -1 : seg[1].diff);//注意判断-1情况
    }
}

嗯，如果不理解的话，可以往上再翻一遍代码理解一下，如果还是不懂，可以离开了（逃

警告：接下来的内容可能会引起蒟蒻不适

Zoo

Description

## Input 第一行，两个整数$N,M$。第二行，$N$个整数$A_i$。$(1\leq A_i\leq 2^{31}-1)$。此后$M$行，每行描述一次投喂。第$t+2$行的三个数$I,J,K$表示在第$t$次投喂中，西西选择了区间$[I,J]$内觅食能力值第$K$强的狮子进行投喂。 ## Output 输出文件有$M$行，每行一个整数。第$i$行的整数表示在第$i$次投喂中吃到食物的狮子的觅食能力值。 ## Sample Input ```plain 7 2 1 5 2 6 3 7 4 1 5 3 2 7 1 ``` ## Sample Output ```plain 3 2 ``` ## Data Constraint 对于$100\%$的数据，有$1\leq N\leq 10^5,1\leq M\leq 5\times 10^4$。 ## 来源 JZOJ ## Analysis 分析 # 权值线段树 UPD on 2020.8.19 由于区间互不包含，所以如果把询问对左端点排序，那么右端点也一定是单调递增的，所以可以直接考虑左右端点的增删量并维护一棵权值线段树……然后就做完了（至于为什么加这一段文字大概是因为好像有学弟翻到了这篇黑历史呢（ # 可持久化线段树/主席树主席树的主要思想就是：保存每次插入操作时的历史版本，以便查询区间第$k$小。怎么保存呢？暴力一点，每次开一棵线段树呗。那空间还不爆掉？那么我们分析一下，发现每次修改操作修改的点的个数是一样的。（例如下图，修改了$[1,8]$中对应权值为$1$的结点，红色的点即为更改的点） ![](https://i.loli.net/2018/08/04/5b6503acf15f9.png) 只更改了$O(\log{n})$个结点，形成一条链，也就是说每次更改的结点数$\ =\ $树的高度。注意主席树不能使用堆式存储法，就是说不能用$x\times 2,x \times 2 + 1$来表示左右儿子，而是应该动态开点，并保存每个节点的左右儿子编号。所以我们只要在记录左右儿子的基础上存一下插入每个数的时候的根节点就可以持久化辣。我们把问题简化一下：每次求$[1,r]$区间内的$k$小值。怎么做呢？只需要找到插入$r$时的根节点版本，然后用普通权值线段树做就行了，如果不会用普通权值线段树做的话请参见开头部分的解释。那么这个相信大家很简单都能理解，把问题扩展到原问题——求$[l,r]$区间$k$小值。这里我们再联系另外一个知识理解：**前缀和**。它运用了区间减法的性质，通过预处理从而达到$O(1)$回答每个询问。那么我们主席树也行！如果需要得到$[l,r]$的统计信息，只需要用$[1,r]$的信息减去$[1,l - 1]$的信息就行了（请好好地想一想是不是如此）那么至此，该问题解决！（完结撒花）关于空间问题，我们分析一下：由于我们是动态开点的，所以一棵线段树只会出现$2n-1$个结点。然后，有$n$次修改，每次增加$\log{n}$个结点。那么最坏情况结点数会达到$2n-1+n\log{n}$，那么此题的$n \leq 10^5$，通过计算得到$\lceil\log_2{10^5}\rceil=17$，那么把$n$和$\log$的结果代入这个式子，变成$2\times 10^5-1+17 \times 10^5$，忽略掉$-1$，大概就是$19 \times 10^5$。算了这么一大堆，$\mathrm{I\ tell\ you:}$ 千万不要吝啬空间！保守一点，直接上个$2^5 \times 10^5 = 32 \times 10^5$，接近原空间的两倍（即`n << 5`）。（较真的同学请注意，如果你真的很吝啬，可以自己造个数据输出一下结点数量，但是如果数据没造好把自己卡掉了就~~尴尬了~~赖你了） P.S: 实测该题需要开到$20n+10$个结点，$19n+10$会$Wonderful\ Answer\ 80pts$，该程序对于$N = 10^5$的数据开到了$1968911$个结点，大于$19n+10$。代码： ```cpp #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn = 1e5;//数据范围 int tot,n,m; int sum[(maxn << 5) + 10],rt[maxn + 10],ls[(maxn << 5) + 10],rs[(maxn << 5) + 10]; int a[maxn + 10],ind[maxn + 10],len; inline int getid(const int &val)//离散化 { return lower_bound(ind + 1,ind + len + 1,val) - ind; } int build(int l,int r)//建树 { int root = ++tot; if(l == r) return root; int mid = l + r >> 1; ls[root] = build(l,mid); rs[root] = build(mid + 1,r); return root;//返回该子树的根节点 } int update(int k,int l,int r,int root)//插入操作 { int dir = ++tot; ls[dir] = ls[root],rs[dir] = rs[root],sum[dir] = sum[root] + 1; if(l == r) return dir; int mid = l + r >> 1; if(k <= mid) ls[dir] = update(k,l,mid,ls[dir]); else rs[dir] = update(k,mid + 1,r,rs[dir]); return dir; } int query(int u,int v,int l,int r,int k)//查询操作 { int mid = l + r >> 1,x = sum[ls[v]] - sum[ls[u]];//通过区间减法得到左儿子的信息 if(l == r) return l; if(k <= x)//说明在左儿子中 return query(ls[u],ls[v],l,mid,k); else//说明在右儿子中 return query(rs[u],rs[v],mid + 1,r,k - x); } inline void init() { scanf("%d%d",&n,&m); for(register int i = 1;i <= n;++i) scanf("%d",a + i); memcpy(ind,a,sizeof ind); sort(ind + 1,ind + n + 1); len = unique(ind + 1,ind + n + 1) - ind - 1; rt[0] = build(1,len); for(register int i = 1;i <= n;++i) rt[i] = update(getid(a[i]),1,len,rt[i - 1]); } int l,r,k; inline void work() { while(m--) { scanf("%d%d%d",&l,&r,&k); printf("%d\n",ind[query(rt[l - 1],rt[r],1,len,k)]);//回答询问 } } int main() { init(); work(); return 0; } ``` ### 鸣谢 - @[孤独·粲泽](/space/show?uid=50871) 大佬的主席树博客 - 其他写了主席树模板题解的大佬 - @[EternalAlexander](/space/show?uid=48355) 大佬之作[OI Painter](/blog/SkeletonSerpent/post-xing-xuan-qian-xi-kai-gong-cheng-oi-painter)提供的绘图便利 - [SM.MS](https://sm.ms)提供的图床 ### 尾声希望读了这篇文章的您能有收获，如果有不懂的，可以私信我，我会完善我的文章，争取让每个人都能读懂！（前提是您要了解前置知识）