[关闭]
@Venous 2018-02-22T21:45:47.000000Z 字数 4913 阅读 954

主席树

知识体系
未经允许，不得转载

前言

翻了半天博客都只有代码和千篇一律的讲解，许多细节性的处理都无法理解，只好求教大牛来理解，为了防止其余OIer在此上耗费时间，故写一篇主席树学习心得
安利一篇别人的好的博客(就是有点亮)
安利一发自己的好博客

谈谈我自己的理解

在学主席树前，你首先要对线段树十分理解
建议你先入门一下，免得许多定义看不懂，如是大佬请忽视

所谓主席树呢，就是对原来的数列[1..n]的每一个前缀[1..i]（1≤i≤n）建立一棵线段树，线段树的每一个节点存某个前缀[1..i]中属于区间[L..R]的数一共有多少个（比如根节点是[1..n]，一共i个数，sum[root] = i；根节点的左儿子是[1..(L+R)/2]，若不大于(L+R)/2的数有x个，那么sum[root.left] = x）。若要查找[i..j]中第k大数时，设某结点x，那么x.sum[j] - x.sum[i - 1]就是[i..j]中在结点x内的数字总数。而对每一个前缀都建一棵树，会MLE，观察到每个[1..i]和[1..i-1]只有一条路是不一样的，那么其他的结点只要用回前一棵树的结点即可，时空复杂度为O(nlogn)。

先讲静态主席树吧，来一波数据,方便理解
我们约定如下：
1.所有区间形式都如同线段树
2. 表示第a个数到第b个数(经过排序后的数组，也就是下文中提到的"现在序列"，实际上也就是值域但是被离散化了)
3. 表示某个区间现在被多少数占有，是包括之前所计算过的(说人话：现在有多少个数已经出现在这个区间所代表的值域中)
4. 表示前i个数所代表的那棵线段树的顶点编号是

输入格式：第一行输入数字个数n,第二行输入n个数

6
13 14 17 15 11 12 (原序列)
3 4 6 5 1 2 (现在序列)

对于前1个数，也就是13,所对其在有空间的贡献是
[1,6] -> 1
[1,3] -> 1
[3,3] -> 1
对于前2个数，也就是13,14,所对其在有空间的贡献是
[1,6] ->2
[1,3] ->1 [4,6] ->1
[3,3] ->1 [4,5] ->1
[4,4] ->1
对于前3个数,也就是13,14,17,所对其在有空间的贡献是
[1,6] ->3
[1,3] ->1 [4,6] ->2
[3,3] ->1 [4,5] ->1 [6,6] ->1
[4,4] ->1

Wait，应同学建议，在此补一则提示：大家先打住，有没有发现其实很多区间我们是重复出现了的，例如“前一个数中的”和“前两个数中的”是一模一样的呢？这便是主席树一个十分优(dan)良(teng)的性质，对于前i个数和前j个数来说，存在某些区间是重复的，可以直接继承过来，不必为此浪费时间与空间

主席树就是利用函数式编程的思想来使线段树支持询问历史版本、同时充分利用它们之间的共同数据来减少时间和空间消耗的增强版的线段树。

以此类推(重复出现的不再累赘)

推荐自己画个图，如是大佬请忽视
对于前4个数,也就是13,14,17,15所对其在有空间的贡献是
[1,6]包含了4个数了
[4,6]包含了3个数了
[4,5]包含了2个数了
[5,5]包含了1个数了
对于前5个数,也就是13,14,17,15,11所对其在有空间的贡献是
[1,6]包含了5个数了
[1,3]包含了2个数了
[1,2]包含了1个数了
[1,1]包含了1个数了
对于前6个数,也就是13,14,17,15,11,12所对其在有空间的贡献是
[1,6]包含了6个数了
[1,3]包含了3个数了
[1,2]包含了2个数了
[2,2]包含了1个数了

看到这里，大家应该明白了吧

主席树线段树

我们若要询问[1,3]中第2小的是多少？
我们怎样寻找区间第2小，因为线段树中的叶节点从左到右表示的数依次增大，根据这个性质，以及每个节点保存了区间内的数的个数这个信息，我们可以轻易的找出区间第2小，具体的找法是，从根节点开始，看左儿子里面的数的个数是不是大于等于2，如果是则第2小一定在左子树中，于是继续找左子树，反之找右子树，直到找到叶节点为止，然后直接返回叶节点表示的值就行。
但是多次询问区间第k小，我们每次这样建立一个线段树，这样不仅空间复杂度非常之高，而且时间复杂度也非常高，甚至比普通排序还要高，那么我们只不是可以想一个办法，使得对于每次我们查询不同的区间我们不需要重新建树，如果这样。时间复杂度和空间复杂度就大大降低了。
我们很容易就联想到了前缀和的概念，比如我们有一个问题。就是每次静态的求区间和，我们可以预处理所以的前缀和sum[i]，我们每次求解区间l,r时，我们可以直接得到答案为sum[r]-sum[l-1],这样就不需要对区间中的每个数进行相加来求解了。
大家应该更能理解为什么主席树要做前缀和了吧
而主席树就能够做到之上的骚操作，并且由于主席树的左右儿子是不确定有没有的，所以不能像线段树一样(lson=now<<1)这样递归找左右儿子(而是看下文)

现在重要的是我们怎么让这些线段树并到一起，主要问题就是我们要快速找到某个区间的那棵线段树呢？这就需要我们统计每个区间的编号了

骚操作一:

  1. tr[++cnt]=tr[now];now=cnt;
  2. //对于每一个区间进行编号，历史版本也需要标号！

骚操作二：

  1. if(k<=mid)update(l,mid,k,tr[now].lson);
  2. else update(mid+1,r,k,tr[now].rson);

Wait，应同学建议，在此补一则提示：大家先打住，有没有发现我们进行修改时实际上只有logn次呢？的确，在每次对某一棵线段树进行修改时，我们实际上影响的只有某条链上的贡献(具体可参照上文样例)，它绝不会从这条链跨到另一条链上，因此证明了时间是O(logn)的

骚操作三：

  1. root[i]=root[i-1];
  2. update(1,n,rank[i],root[i]);
  3. //先直接把前一棵线段树传过来，再进行修改某些需要修改的区间

为了方便读者理解，笔者将所有区间(包括历史版本)的顶点标号都打表了出来

[1,6]的编号为:1,包含了 1个数了
[1,3]的编号为:2,包含了 1个数了
[3,3]的编号为:3,包含了 1个数了
root[1]=1
[1,6]的编号为:4,包含了 2个数了
[4,6]的编号为:5,包含了 1个数了
[4,5]的编号为:6,包含了 1个数了
[4,4]的编号为:7,包含了 1个数了
root[2]=4
[1,6]的编号为:8,包含了 3个数了
[4,6]的编号为:9,包含了 2个数了
[6,6]的编号为:10,包含了 1个数了
root[3]=8
[1,6]的编号为:11,包含了 4个数了
[4,6]的编号为:12,包含了 3个数了
[4,5]的编号为:13,包含了 2个数了
[5,5]的编号为:14,包含了 1个数了
root[4]=11
[1,6]的编号为:15,包含了 5个数了
[1,3]的编号为:16,包含了 2个数了
[1,2]的编号为:17,包含了 1个数了
[1,1]的编号为:18,包含了 1个数了
root[5]=15
[1,6]的编号为:19,包含了 6个数了
[1,3]的编号为:20,包含了 3个数了
[1,2]的编号为:21,包含了 2个数了
[2,2]的编号为:22,包含了 1个数了
root[6]=19

这样相信读者理解主席树的多棵线段树骚操作了吧
(尽情参考上文样例)

好了，到这里我们已经解决了线段树的问题了，现在开始理解是怎么做到静态查询区间第k大的

  1. int query(int l,int r,int i,int j,int k)
  2. {
  3.     int d=tr[tr[j].lson].sum-tr[tr[i].lson].sum;
  4.     //看左儿子之差是否满足k的限制
  5.     if(l==r)return l;
  6.     if(k<=d)return query(l,mid,tr[i].lson,tr[j].lson,k);
  7.     else return query(mid+1,r,tr[i].rson,tr[j].rson,k-d);
  8. }
  9. //具体情况已于上文介绍"我们若要询问[1,3]中第2小的是多少？"

好了，可能还有一些细节没有讲到，大家尽情参考代码吧

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. #define mid ((l+r)>>1)
  7. const int _=1e5+5;
  8. inline int read()
  9. {
  10.     char ch='!';int z=1,num=0;
  11.     while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
  12.     if(ch=='-')z=-1,ch=getchar();
  13.     while(ch<='9'&&ch>='0')num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
  14.     return z*num;
  15. }
  16. int n,m;
  17. struct hand{int x,id;}a[_];
  18. struct some{int lson,rson,sum;}tr[_*20];
  19. //sum表示在前i个数里管辖[l,r]的有多少个数,即值域属于[l,r]的有多少个数在该区间里
  20. bool cmp(hand A,hand B){return A.x<B.x;}
  21. int cnt,rank[_],root[_];
  22. //root[]表示多棵线段树的根节点
  23. void init()
  24. {
  25.     root[0]=0;
  26.     tr[0].lson=tr[0].rson=tr[0].sum=0;
  27. }
  28. //我需要知道我的lson和rson是从哪里转移过来的
  29. void update(int l,int r,int k,int &now)
  30. {
  31.     tr[++cnt]=tr[now];
  32.     //节省了许多空间，的确，单次插入都是相当于一条链上操作
  33.     //故空间上顶多开log级别(只有log次需要我们新开线段树)
  34.     now=cnt;
  35.     tr[now].sum++;
  36.     if(l==r)return;
  37.     if(k<=mid)update(l,mid,k,tr[now].lson);
  38.     else update(mid+1,r,k,tr[now].rson);
  39. }
  40. //实际上tr[x].lson记录的是以x为根的线段树的左儿子的节点编号
  41. //因为许多儿子节点都是借用的，所以如果不记录的话就会错认成没有儿子
  42. int query(int l,int r,int i,int j,int k)
  43. {
  44.     int d=tr[tr[j].lson].sum-tr[tr[i].lson].sum;
  45.     //i,j是两棵线段树的编号，只不过版本不同(一种是在前i个的版本，一种是在前j个的版本)，但是相对位置是相同的，例如[1,3]对[1,3]
  46.     //这样就满足用前缀和来做加减操作了
  47.     if(l==r)return l;
  48.     if(k<=d)return query(l,mid,tr[i].lson,tr[j].lson,k);
  49.     //左儿子不够k个，说明我们需要查的数在右儿子区间里，注意“k-d“，因为左儿子的贡献d还是要算上的
  50.     else return query(mid+1,r,tr[i].rson,tr[j].rson,k-d);
  51.     //为了保证相对位置相同，必须同时向左或向右跳
  52. }
  53. int main()
  54. {
  55.     n=read();m=read();
  56.     for(int i=1;i<=n;i++)
  57.     {
  58.         a[i].x=read();
  59.         a[i].id=i;
  60.     }
  61.     sort(a+1,a+1+n,cmp);
  62.     for(int i=1;i<=n;i++)
  63.     {
  64.         rank[a[i].id]=i;
  65.     }
  66.     init();
  67.     for(int i=1;i<=n;i++)
  68.     {
  69.         root[i]=root[i-1];
  70.         update(1,n,rank[i],root[i]);
  71.     }int l,r,k;
  72.     while(m--)
  73.     {
  74.         l=read();r=read();k=read();
  75.         printf("%d\n",a[query(1,n,root[l-1],root[r],k)].x);
  76.     }
  77.     return 0;
  78. }

好了，静态主席树就到此讲完了
(至于动态主席树的坑可能要留到以后补了)

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注