主席树-白红宇

主席树

阅读量：5097 次

发布时间：2019-06-13

本文共 2816 字，大约阅读时间需要 9 分钟。

先%fotile主席

话说本蒟蒻一直布吉岛主席树与可持久化线段树的区别。。。也许他们就是一个东西。。。

首先

很明显的，如果我们要在原线段树上进行一次单点修改，并将新的树保存下来，我们其实可以不用新建2n个空间，我们可以注意到，每修改一次单点，只对从根到那个叶节点路径上的点有影响，所以我们新建一棵树只需logn的空间开销，正如图中所示，我们把新的节点的另一个儿子，指向老的节点的一个儿子即可(由于是修改，线段树的结构是完全一样的，只是这logn个节点维护的信息不一样罢了。

我结构体是这样定义：

struct Node {	int sum;	Node *l, *r;	Node (int sum = 0, Node *l = Null, Node *r = Null) : sum(sum), l(l), r(r) {}}*root[N], meme[N * 100], *pool = meme;

我们可以这样修改：

Node *Modify (Node *A, int l, int r, int x, int data) {	if (l == r) return newnode (A -> sum + data, Null, Null);	int mid = (l + r) >> 1;	if (x > mid) return newnode (A -> sum + data, A -> l, Modify (A -> r, mid + 1, r, x, data));	return newnode (A -> sum + data, Modify (A -> l, l, mid, x, data), A -> r);}

修改后返回的值就是新树的根辣！

请把上面的修改看懂。。。

那么问题来了，说了这么多也没扯上什么是主席树啊。。。。

我先通过一道题来解释吧，求区间第k小，如果是前缀第k小，普通权值线段树是可做的吧。

我们可以对于一个长度为n的序列，建立n棵(主席)树 (当然要先建一棵空的主席(线段)树，设这为第0棵树，然后第i棵(主席)树根据第i-1棵(主席)树按刚才的方法建出)。由于所有的(主席)树的结构都是相同的，我们可以直接对他们代表同一段权值的节点作减法(比如我们要查询一段区间[l,r]，我们可以用r代表一段权值的节点减去l-1代表这一段权值的节点，所得的信息就是[l,r]这段区间的这段权值的信息，r代表这一段权值的节点储存前r个的信息，l代表这一段权值的节点储存前l-1这一段的信息)。然后根据这个就可以求区间第k大了。。。 (因为我是蒟蒻，如果有不详细的地方请指出，以便我修正)

上代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
            #include
            
             const int N = 3e4 + 7; struct Node *Null;struct Node { int sum; Node *l, *r; Node (int sum = 0, Node *l = Null, Node *r = Null) : sum(sum), l(l), r(r) {}}*root[N], meme[N * 100], *pool = meme;Node *newnode (int sum, Node *l, Node *r) { return new (pool++) Node (sum, l, r);}Node *Build_Null (int l, int r) { if (l == r) return newnode (0, Null, Null); int mid = (l + r) >> 1; return newnode (0, Build_Null (l, mid), Build_Null (mid + 1, r));}Node *Modify (Node *A, int l, int r, int x, int data) { if (l == r) return newnode (A -> sum + data, Null, Null); int mid = (l + r) >> 1; if (x > mid) return newnode (A -> sum + data, A -> l, Modify (A -> r, mid + 1, r, x, data)); return newnode (A -> sum + data, Modify (A -> l, l, mid, x, data), A -> r);}int Query (Node *x, int l, int r, int k) { if (k == (r - l + 1)) return 0; if (!k) return x -> sum; int mid = (l + r) >> 1; if (k <= mid - l + 1) return Query (x -> l, l, mid, k) + x -> r -> sum; return Query (x -> r, mid + 1, r, k - mid + l - 1);}int a, n, m, x1, x2;using std :: map;map 
             
               tem;Node *tt;int main () { Null = new Node (0, NULL, NULL); scanf ("%d", &n); root[0] = Build_Null (1, n); for (int i = 1; i <= n; ++i) { scanf ("%d", &a); if (!tem.count(a)) tt = root[i-1]; else tt = Modify (root[i-1], 1, n, tem[a], -1); root[i] = Modify (tt, 1, n, i, 1); tem[a] = i; } scanf ("%d", &m); for (int i = 1; i <= m; ++i) { scanf ("%d%d", &x1, &x2); printf ("%d\n", Query (root[x2], 1, n, x1 - 1)); } return 0;}

转载于:https://www.cnblogs.com/dcoi-king/p/7491435.html

你可能感兴趣的文章