Dyd's Blog

He who has a strong enough why can bear almost any how.

主席树

Posted on In
Symbols count in article: 4.4k Reading time ≈ 4 mins.

就是可持久化线段树

主席树

名字似乎有点来历，但懒得考究了，发现同机房就我这个蒟蒻还不会，所以来补补

普通

其实就是可持久化线段树，这里说几个个人认为的要点：

  1. 最初的树不必一个个插，可以直接建
  2. 区间修改的化必须标记永久化
  3. 空间要开够，大概是 $O(4n + m \log n)$ 的

这里给出一个实现（最快的用时是我的一半，我是大常数选手实锤了）：

可持久化线段树 2

就是维护静态区间第 $k$ 大，建值域线段树，把每个点依次加入然后线段树上二分即可， $O(n \log n)$ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
#define pb push_back
const int N = 2e5 + 100;
int n, num, m;
int a[N];
std::vector<int> xx;
void lsh()
{
    xx.reserve(n + 1);
    xx.pb(-1);
    for (int i = 1; i <= n; ++i) xx.pb(a[i]);
    std::sort(xx.begin(), xx.end());
    xx.erase(std::unique(xx.begin(), xx.end()), xx.end());
    for (int i = 1; i <= n; ++i) a[i] = std::lower_bound(xx.begin(), xx.end(), a[i]) - xx.begin();
    num = xx.size();
}
namespace CT //Chairman Tree
{
    const int NN = 5e6 + 100;
    struct Node{ int lc, rc, dat; } tr[NN];
    int rt[N], tot = 0;
    #define lc(x) tr[(x)].lc
    #define rc(x) tr[(x)].rc
    #define dat(x) tr[(x)].dat
    #define mid ((l + r) >> 1)
    void bd(int &u, int l = 1, int r = num)
    {
        u = ++tot;
        tr[u] = {0, 0, 0};
        if (l < r) bd(lc(u), l, mid), bd(rc(u), mid + 1, r);
    }
    void cg(int pos, int d, int &u, int la, int l = 1, int r = num)
    {
        u = ++tot;
        tr[u] = tr[la];
        dat(u) += d;
        if (l == r) return ;
        (pos <= mid) ? cg(pos, d, lc(u), lc(la), l, mid) : cg(pos, d, rc(u), rc(la), mid + 1, r);
    }
    int ask(int ul, int ur, int k, int l = 1, int r = num)
    {
        if (l == r) return l;
        int t = dat(lc(ur)) - dat(lc(ul));
        return (t >= k) ? ask(lc(ul), lc(ur), k, l, mid) : ask(rc(ul), rc(ur), k - t, mid + 1, r);
    }
    #undef lc
    #undef rc
    #undef dat
    #undef mid 
}
using CT::rt;
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    lsh(), CT::bd(rt[0]);
    for (int i = 1; i <= n; ++i) CT::cg(a[i], 1, rt[i], rt[i - 1]);
    for (int l, r, k; m--; )
    {
        scanf("%d %d %d", &l, &r, &k);
        printf("%d\n", xx[CT::ask(rt[l - 1], rt[r], k)]);
    }
    return 0;
}

带修

看看这个：

Dynamic Rankings

上面问题的带修版本

直接考虑把主席树套到树状数组上（反正 BIT 擅长维护前缀和），代码也很好写，时空都是 $O(n \log^2 n)$

实现的时候，由于套上的一个 BIT 不好建最初的树，反正那棵树里面啥都没有，就懒得建了（其实感觉已经不是主席树，或者可持久化线段树了，因为没有从上一个状态继承，而是完全动态开点），一个要点是 BIT 是建在“时间“上的，大小该是 $n$ ，而主席树是建在值域上的、

代码（我常数过大被整体二分做法吊打）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
#define pb push_back
const int N = 1e5 + 100;
int n, m, num;
int a[N];
struct Q{ int op, l, r, k; } q[N];
std::vector<int> xx;
void lsh()
{
    xx.reserve(n + m + 1);
    xx.pb(-1);
    for (int i = 1; i <= n; ++i) xx.pb(a[i]);
    for (int i = 1; i <= m; ++i) if (!q[i].k) xx.pb(q[i].r);
    std::sort(xx.begin(), xx.end());
    xx.erase(std::unique(xx.begin(), xx.end()), xx.end());
    for (int i = 1; i <= n; ++i) a[i] = std::lower_bound(xx.begin(), xx.end(), a[i]) - xx.begin();
    for (int i = 1; i <= m; ++i) if (!q[i].k) q[i].r = std::lower_bound(xx.begin(), xx.end(), q[i].r) - xx.begin();
    num = xx.size();
}
namespace BIT
{
    const int NN = 6e7 + 100, D = 20;
    int rts[2][D];
    namespace CT
    {
        struct Node{ int lc, rc, cnt; } tr[NN];
        int rt[N], tot = 0;
        #define lc(x) tr[(x)].lc
        #define rc(x) tr[(x)].rc
        #define ct(x) tr[(x)].cnt
        #define mid ((l + r) >> 1)
        void cg(int pos, int d, int &u, int l = 1, int r = num)
        {
            if (!u) u = ++tot;
            ct(u) += d;
            if (l == r) return ;
            (pos <= mid) ? cg(pos, d, lc(u), l, mid) : cg(pos, d, rc(u), mid + 1, r);
        }
        int ask(int k, int l = 1, int r = num)
        {
            if (l == r) return l;
            int sum = 0;
            for (int i = rts[1][0]; i; --i) sum += ct(lc(rts[1][i]));
            for (int i = rts[0][0]; i; --i) sum -= ct(lc(rts[0][i]));
            if (sum >= k)
            {
                for (int i = rts[1][0]; i; --i) rts[1][i] = lc(rts[1][i]);
                for (int i = rts[0][0]; i; --i) rts[0][i] = lc(rts[0][i]);
                return ask(k, l, mid);
            }
            else
            {
                for (int i = rts[1][0]; i; --i) rts[1][i] = rc(rts[1][i]);
                for (int i = rts[0][0]; i; --i) rts[0][i] = rc(rts[0][i]);
                return ask(k - sum, mid + 1, r);
            }
        }
        #undef lc
        #undef rc
        #undef ct
        #undef mid
    }
    using CT::rt;
    #define lb(x) ((x) & (-(x)))
    void cg(int x, int d){ for (int i = x; i <= n; i += lb(i)) CT::cg(a[x], d, rt[i]); }
    int ask(int l, int r, int k)
    {
        rts[0][0] = rts[1][0] = 0;
        for (int i = r; i; i ^= lb(i)) rts[1][++rts[1][0]] = rt[i];
        for (int i = l - 1; i; i ^= lb(i)) rts[0][++rts[0][0]] = rt[i];
        return CT::ask(k);
    }
    #undef lb
}
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= m; ++i)
    {
        char c[2];
        scanf("%s", c);
        if (c[0] == 'Q') scanf("%d %d %d", &q[i].l, &q[i].r, &q[i].k);
        else scanf("%d %d", &q[i].l, &q[i].r);
    }
    lsh();
    for (int i = 1; i <= n; ++i) BIT::cg(i, 1);
    for (int i = 1; i <= m; ++i) 
        if (q[i].k) printf("%d\n", xx[BIT::ask(q[i].l, q[i].r, q[i].k)]);
        else 
        {
            BIT::cg(q[i].l, -1);
            a[q[i].l] = q[i].r;
            BIT::cg(q[i].l, 1);
        }   
    return 0;
}