发表更新OI笔记18 分钟读完 (大约2641个字)

主席树

众所周知，主席树即可持久化值域线段树， 用于解决区间 $k$ 小值问题以及动态二维数点问题。

1 静态主席树

静态区间 k 小值

给定 $n$ 个整数构成的序列 $a$，将对于指定的闭区间 $[l, r]$ 查询其区间内的第 $k$ 小值。

静态主席树一般指可持久化值域线段树，并不支持修改操作。

容易发现区间信息是满足可减性的，则只需要在每次插入时建立一个船新版本即可，查询也只需要对两个历史版本作差便能得到区间信息。
类似的，01-Trie 与 Treap 之类的无法维护区间信息的数据结构也可以通过可持久化来实现区间信息的维护。

容易得出下面的这份代码实现：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int CN = 2e5 + 5;

int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

class SGT{
  public: int d[CN * 50], rt[CN * 50], ch[CN * 50][2], idx;
    #define lc ch[u][0]
    #define rc ch[u][1]
    SGT() {idx = 0;}
    int make() {return ++idx;}
    void md(int &u, int v, int l, int r, int p){
        if(!u) u = make();
        if(l == r) return (void)(d[u] = d[v] + 1);
        int m = (l + r) >> 1;
        if(p <= m) md(lc, ch[v][0], l, m, p), rc = ch[v][1]; 
        else md(rc, ch[v][1], m + 1, r, p), lc = ch[v][0];
        d[u] = d[lc] + d[rc];
    }
    int qu(int u, int v, int l, int r, int k){
        if(l == r) return l;
        int m = (l + r) >> 1, s = d[lc] - d[ ch[v][0] ];
        if(s >= k) return qu(lc, ch[v][0], l, m, k);
        else return qu(rc, ch[v][1], m + 1, r, k - s);
    }
} D;

int n, m, a[CN], val[CN];
int id(int x) {return lower_bound(val + 1, val + val[0] + 1, x) - val;}

int main()
{
    freopen("_in.in", "r", stdin);

    n = read(), m = read(); for(int i = 1; i <= n; i++) val[i] = a[i] = read();

    sort(val + 1, val + n + 1);
    val[0] = 1; for(int i = 2; i <= n; i++) if(val[i] ^ val[i - 1]) val[ ++val[0] ] = val[i];

    for(int i = 1; i <= n; i++) D.md(D.rt[i], D.rt[i - 1], 1, val[0], id( a[i] ));
    while(m--){
        int l = read(), r = read(), k = read();
        printf("%d", val[ D.qu( D.rt[r], D.rt[l - 1], 1, val[0], k ) ]), puts("");
    }
}

2 带修主席树

动态区间 k 小值

给定一个含有 $n$ 个数的序列 $a_1, a_2, …, a_n$ ，需要支持两种操作：

  • Q l r k 表示查询下标在区间 $[l,r]$ 中的第 $k$ 小的数
  • C x y 表示将 $a_x$ 改为 $y$

带修主席树一般指树状数组套可持久化值域线段树。

容易发现主席树的每个版本是对区间信息做一个前缀和，这样如果在某个版本上修改是 $O(n)$ 的。
既然是前缀和，套用树状数组的方式写主席树就好了，复杂度 $O(n\log^2n)$ 。

于是容易得到下面的这份代码实现：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int CN = 4e5 + 5;

int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

class SGT{
  public: int d[CN * 50], ch[CN * 50][2], rt[CN], idx, n;
    #define lc ch[u][0]
    #define rc ch[u][1]
    SGT() {idx = 0;}
    int make() {return ++idx;}
    int lb(int x) {return x & (-x);}
    void md(int &u, int l, int r, int p, int x){ // 修改不新建版本
        if(!u) u = make();
        if(l == r) return (void)(d[u] += x);
        int m = (l + r) >> 1;
        if(p <= m) md(lc, l, m, p, x); else md(rc, m + 1, r, p, x);
        d[u] = d[lc] + d[rc];
    }
    void cg(int u, int p, int x){ // 修改 BIT 中所有的树
        while(u <= rt[0]) md(rt[u], 1, n, p, x), u += lb(u);
    }
    int t1[101], t2[101]; // 把 O(log) 棵主席树的根搞下来
    void qu_pre(int l, int r){ // (l, r]
        t1[0] = t2[0] = 0;
        int u = l; while(u) t1[ ++t1[0] ] = rt[u], u -= lb(u);
        u = r; while(u) t2[ ++t2[0] ] = rt[u], u -= lb(u);
    }
    int qu(int l, int r, int k){
        if(l == r) return l;
        int m = (l + r) >> 1, s = 0;
        for(int i = 1; i <= t1[0]; i++) s -= d[ ch[ t1[i] ][0] ];
        for(int i = 1; i <= t2[0]; i++) s += d[ ch[ t2[i] ][0] ];
        if(s >= k){
            for(int i = 1; i <= t1[0]; i++) t1[i] = ch[ t1[i] ][0];
            for(int i = 1; i <= t2[0]; i++) t2[i] = ch[ t2[i] ][0];
            return qu(l, m, k);
        }
        else{
            for(int i = 1; i <= t1[0]; i++) t1[i] = ch[ t1[i] ][1];
            for(int i = 1; i <= t2[0]; i++) t2[i] = ch[ t2[i] ][1];
            return qu(m + 1, r, k - s);
        }
    }
} D;

class QUERY {
  public: int tp, a, b, c;
} Q[CN];

int n, m, a[CN], val[CN];
int id(int x) {return lower_bound(val + 1, val + val[0] + 1, x) - val;}

int main()
{
    freopen("_in.in", "r", stdin);

    D.rt[0] = n = read(), m = read();
    for(int i = 1; i <= n; i++) val[ ++val[0] ] = a[i] = read();
    for(int i = 1; i <= m; i++) {
        char c; cin >> c;
        if(c == 'Q') Q[i].tp = 0, Q[i].a = read(), Q[i].b = read(), Q[i].c = read();
        else Q[i].tp = 1, Q[i].a = read(), val[ ++val[0] ] = Q[i].b = read();
    }

    sort(val + 1, val + val[0] + 1); int cnt = 1;
    for(int i = 2; i <= val[0]; i++) if(val[i] ^ val[i - 1]) val[ ++cnt ] = val[i];
    D.n = val[0] = cnt;

    for(int i = 1; i <= n; i++) D.cg(i, id( a[i] ), 1);

    for(int i = 1; i <= m; i++){
        if(!Q[i].tp){
            D.qu_pre(Q[i].a - 1, Q[i].b);
            printf("%d", val[ D.qu(1, val[0], Q[i].c) ]), puts("");
        }
        else
            D.cg(Q[i].a, id( a[ Q[i].a ] ), -1), a[ Q[i].a ] = Q[i].b, D.cg(Q[i].a, id( a[ Q[i].a ] ), 1);
    }
}

由于代码中各种空间跳跃以及频繁出现的 Cache-Miss ，导致其常数巨大，不过它依然能在 1s 左右的时间内通过此题。

3 一道栗题

「CQOI2011」动态逆序对

给出 $1\sim n$ 的一个排列，按照某种顺序依次删除 $m$ 个元素，在每次删除一个元素之前统计整个序列的逆序对数。

如果是静态问题，那么只需要用权值树状数组就可以简单维护。

由于只有删除操作，考虑计算删除一个元素对答案的贡献（实际上是减少量而不是增加量），容易发现这样的查询同时存在下标和权值两个维度；下标即通过版本来区分，因此用主席树。考虑到修改和影响传递的过程，仿照上题套一个树状数组即可。

于是容易得到如下代码。同样的，由于代码中各种空间跳跃以及频繁出现的 Cache-Miss ，其常数巨大，不过它依然能在 1.2s 左右的时间内通过此题。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

#define LL long long

const int CN = 2e5 + 5;

int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

class SGT{
  public: int d[CN * 50], rt[CN], ch[CN * 50][2], idx, n;
    #define lc ch[u][0]
    #define rc ch[u][1]
    SGT() {idx = 0;}
    int make() {return ++idx;}
    int lb(int x) {return x & (-x);}
    void md(int &u, int l, int r, int p, int x){
        if(!u) u = make(); if(l == r) return (void)(d[u] += x);
        int m = (l + r) >> 1;
        if(p <= m) md(lc, l, m, p, x); else md(rc, m + 1, r, p, x);
        d[u] = d[lc] + d[rc];
    }
    void cg(int u, int p, int x){
        while(u <= rt[0]) md(rt[u], 1, n, p, x), u += lb(u);
    }
    int t[CN];
    void pqu(int r){
        t[0] = 0;
        int u = r; while(u) t[ ++t[0] ] = rt[u], u -= lb(u);
    }
    int qu(int l, int r, int p){
        if(l == r){
            int s = 0;
            for(int i = 1; i <= t[0]; i++) s += d[ t[i] ];
            return s; 
        }
        int m = (l + r) >> 1;
        if(p <= m){
            for(int i = 1; i <= t[0]; i++) t[i] = ch[ t[i] ][0];
            return qu(l, m, p);
        }
        else{
            int s = 0;
            for(int i = 1; i <= t[0]; i++) s += d[ ch[ t[i] ][0] ];
            for(int i = 1; i <= t[0]; i++) t[i] = ch[ t[i] ][1];
            return s + qu(m + 1, r, p);
        }
    }
} D;

int n, m, a[CN], val[CN], rk[CN];

int main()
{
    freopen("_in.in", "r", stdin);

    n = read(), m = read();
    for(int i = 1; i <= n; i++) val[i] = a[i] = read(), rk[ a[i] ] = i;
    D.rt[0] = D.n = n;

    LL ans = 0;
    for(int i = 1; i <= n; i++) 
        D.cg(i, a[i], 1), D.pqu(i - 1), ans -= D.qu(1, n, a[i]), D.pqu(i - 1), ans += D.qu(1, n, n);

    m -= 1;
    while(m--){
        printf("%lld", ans), puts("");
        int x = read(), p = rk[x], s1, s2;
        D.cg(p, x, -1);
        D.pqu(p - 1), s2 = D.qu(1, n, x);
        D.pqu(p - 1), s1 = D.qu(1, n, n) - s2;
        D.pqu(n), s2 = D.qu(1, n, x) - s2;
        ans -= s1 + s2;
    }
    
    printf("%lld", ans);
}

4 二维数点

「SHOI2007」园丁的烦恼

维护二维坐标系上的 $n$ 个点，$q$ 次查询矩形 $(a,b):(c,d)$ 内的点的个数。

二维数点是一类宽泛的 RMQ 问题，甚至于许多树上问题都能通过 dfs 序转化成二维数点问题。

众所周知，带修主席树可以用来解决动态二维数点问题，其本质与上面的题目类似。对于静态的二维数点，带修主席树 $O(n\log^2n)$ 的复杂度要比 $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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int CN = 1e6 + 5;

int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

class SGT {
  public: int d[CN * 50], ch[CN * 50][2], rt[CN], idx, n, m;
    #define lc ch[u][0]
    #define rc ch[u][1]
    int make() {return ++idx;}
    int lb(int x) {return x & (-x);}
    void pmd(int &u, int l, int r, int p, int x){
        if(!u) u = make(); if(l == r) return (void)(d[u] += x);
        int m = (l + r) >> 1; if(p <= m) pmd(lc, l, m, p, x); else pmd(rc, m + 1, r, p, x);
        d[u] = d[lc] + d[rc];
    }
    void md(int u, int p, int x) {while(u <= m) pmd(rt[u], 1, n, p, x), u += lb(u);}
    int t1[25], t2[25];
    void pqu(int s, int t){
        int u = s; t1[0] = 0; while(u) t1[ ++t1[0] ] = rt[u], u -= lb(u);
        u = t; t2[0] = 0; while(u) t2[ ++t2[0] ] = rt[u], u -= lb(u); 
    }
    int qu(int l, int r, int s, int t){
        if(s <= l && r <= t){
            int ans = 0;
            for(int i = 1; i <= t2[0]; i++) ans += d[ t2[i] ];
            for(int i = 1; i <= t1[0]; i++) ans -= d[ t1[i] ];
            return ans;
        }
        int m = (l + r) >> 1, ans = 0, tmp1[25], tmp2[25];
        if(s <= m){
            if(m < t) memcpy(tmp1, t1, sizeof(t1)), memcpy(tmp2, t2, sizeof(t2));
            for(int i = 1; i <= t1[0]; i++) t1[i] = ch[ t1[i] ][0];
            for(int i = 1; i <= t2[0]; i++) t2[i] = ch[ t2[i] ][0];
            ans += qu(l, m, s, t);
            if(m < t) memcpy(t1, tmp1, sizeof(tmp1)), memcpy(t2, tmp2, sizeof(tmp2));
        } 
        if(m < t){
            for(int i = 1; i <= t1[0]; i++) t1[i] = ch[ t1[i] ][1];
            for(int i = 1; i <= t2[0]; i++) t2[i] = ch[ t2[i] ][1];
            ans += qu(m + 1, r, s, t);
        }
        return ans;
    }
} D;

int n, m, vX[CN], vY[CN], X[CN], Y[CN];

int idx(int x) {return lower_bound(vX + 1, vX + vX[0] + 1, x) - vX;}
int idy(int x) {return lower_bound(vY + 1, vY + vY[0] + 1, x) - vY;}

class QU {public: int a, b, c, d;} q[CN];

int main()
{
    freopen("_in.in", "r", stdin);

    n = read(), m = read();
    for(int i = 1; i <= n; i++) vX[i] = X[i] = read() + 1, vY[i] = Y[i] = read() + 1; vX[0] = vY[0] = n;
    for(int i = 1; i <= m; i++) vX[ ++vX[0] ] = q[i].a = read() + 1, vY[ ++vY[0] ] = q[i].b = read() + 1, vX[ ++vX[0] ] = q[i].c = read() + 1, vY[ ++vY[0] ] = q[i].d = read() + 1;

    sort(vX + 1, vX + vX[0] + 1), sort(vY + 1, vY + vY[0] + 1); int tmp = 1;
    for(int i = 2; i <= vX[0]; i++) if(vX[i] ^ vX[i - 1]) vX[++tmp] = vX[i]; vX[0] = tmp;
    tmp = 1; for(int i = 2; i <= vY[0]; i++) if(vY[i] ^ vY[i - 1]) vY[++tmp] = vY[i]; vY[0] = tmp;

    D.n = vY[0], D.m = vX[0];
    for(int i = 1; i <= n; i++) D.md( idx( X[i] ), idy( Y[i] ), 1);

    for(int i = 1; i <= m; i++){
        int a = q[i].a, b = q[i].b, c = q[i].c, d = q[i].d;
        D.pqu(idx(a) - 1, idx(c)), printf("%d", D.qu(1, D.n, idy(b), idy(d))), puts("");
    }
}

主席树

https://big-news.cn/2020/08/17/主席树/

作者

ce-amtic

发布于

2020-08-17

更新于

2020-12-27

许可协议

CC BY-NC-SA 4.0

#

评论

目录

推荐阅读

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×