[数据结构与算法]主席树 常见题目类型总结

一、 主席树维护区间第K大

主席树最基础的应用，对于给定的序列建立权值数组，对于每个元素建立一棵主席树，维护$[1,n]$的数字个数(前缀和)。查询时在树上二分查找。对于当前节点判断左子树的节点个数是否满足比$k$大，如果满足则向左递归查询，否则减去左子树节点个数向右子树递归查询。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int a[N], b[N], n, m;
int root[N], tot;
int lc[N << 5], rc[N << 5], sum[N << 5];

void update(int &rt, int pre, int l, int r, int x, int v){
    rt = ++tot, lc[rt] = lc[pre], rc[rt] = rc[pre], sum[rt] = sum[pre] + 1;
    if(l == r) return;
    int mid = l + r >> 1;
    if(x <= mid) update(lc[rt], lc[pre], l, mid, x, v);
    else update(rc[rt], rc[pre], mid + 1, r, x, v);
}

int query(int L, int R, int l, int r, int k){
    if(l == r) return l;
    int summ = sum[lc[R]] - sum[lc[L]], mid = l + r >> 1;
    if(summ >= k) return query(lc[L], lc[R], l, mid, k);
    else return query(rc[L], rc[R], mid + 1, r, k - summ);
}


signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    int n_1 = unique(b + 1, b + 1 + n) - (b + 1);
    for(int i = 1; i <= n; i++){
        update(root[i], root[i - 1], 1, n_1, lower_bound(b + 1, b + 1 + n_1, a[i]) - b, 1);
    }
    for(int i = 1; i <= m; i++){
        int l, r, k; cin >> l >> r >> k;
        cout << b[query(root[l - 1], root[r], 1, n_1, k)] << endl;
    }
    return 0;
}

二、主席树维护线段树区间修改(标记永久化)

主席树可以维护线段树的区间修改，但是要求线段树动态开点。

在区间更新的时候，对每个点打永久化标记，对于跨越区间的点需要直接修改。查询时找到对应的完全覆盖区间加上这个区间的标记*(区间长度)

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5 + 10;
int root[N], lc[N << 6], rc[N << 6], tot = 0, cur = 0;
ll sum[N << 6], lazy[N << 6];
int n, m;

void build(int &rt, int l, int r){
    rt = ++tot, lazy[rt] = 0;
    if(l == r){
        scanf("%lld", &sum[rt]);
        return;
    }
    int mid = l + r >> 1;
    build(lc[rt], l, mid);
    build(rc[rt], mid + 1, r);
    sum[rt] = sum[lc[rt]] + sum[rc[rt]];
}

void update(int &rt, int pre, int l, int r, int L, int R, int c){
    rt = ++tot, lc[rt] = lc[pre], rc[rt] = rc[pre], lazy[rt] = lazy[pre], sum[rt] = sum[pre] + 1ll * (min(r, R) - max(l, L) + 1) * c;
    if(L >= l && R <= r){
        lazy[rt] += c;
        return;
    }
    int mid = L + R >> 1;
    if(l <= mid) update(lc[rt], lc[pre], l, r, L, mid, c);
    if(r > mid) update(rc[rt], rc[pre], l, r, mid + 1, R, c);
}

ll query(int rt, int L, int R, int l, int r){
    if(L >= l && R <= r) return sum[rt];
    int mid = L + R >> 1;
    ll ans = lazy[rt] * (min(r, R) - max(l, L) + 1);
    if(l <= mid) ans += query(lc[rt], L, mid, l, r);
    if(r > mid) ans += query(rc[rt], mid + 1, R, l, r);
    return ans;
}

signed main(){
    while(scanf("%d%d", &n, &m) != EOF){
        char op[10]; 
        cur = tot = 0;
        build(root[0], 1, n);
        while(m--){
            scanf("%s", op);           
            if(op[0] == 'C'){
                int l, r, c;
                scanf("%d%d%d", &l, &r, &c);
                cur++;
                update(root[cur], root[cur - 1], l, r, 1, n, c);
            }
            else if(op[0] == 'Q'){
                int l, r;
                scanf("%d%d", &l, &r);
                printf("%lld\n", query(root[cur], 1, n, l, r));
            }
            else if(op[0] == 'H'){
                int l, r, h;
                scanf("%d%d%d", &l, &r, &h);
                printf("%lld\n", query(root[h], 1, n, l, r));
            }
            else if(op[0] == 'B'){
                scanf("%d", &cur);
            }
        }
    }
    return 0; 
}

三、求区间内不同的数字个数/求区间大于$K$的数字有多少

求区间内不同数字个数的问题可以转化为求区间内小于等于$K$的数字个数：

对于每个数字记录下一个最近的相同数字下标$nxt[i]$，那么查询区间$[L,R]$内不同数字的个数实际上就是在查询区间内$nxt[i]>R$的个数(下一个相同的数字位于区间之外)。那么现在不难发现对于给定区间$[l,r]$，如果$nxt[i]>r,i\in [l,r]$，那么表示与$i$相同数字点位于区间之外。那么求不同数字个数问题便转化为给定求所有满足$l<=i<=r,nxt[i]>r$的个数。

那么我们只需要处理出$nxt$数组，然后用主席树对每个节点维护权值数组，然后区间查询数目即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int a[N], head[N], nxt[N];
int root[N], sum[N << 5], lc[N << 5], rc[N << 5], cnt;

inline int read(){
    int f = 1, x = 0; char s = getchar(); 
    while(s < '0'||s > '9'){ if(s =='-') f = -1; s = getchar(); } 
    while(s >= '0' && s <= '9'){ x = x * 10 + s - '0'; s = getchar();}
    return x *= f; 
}

void build(int &rt, int l, int r){
    rt = ++cnt;
    if(l == r) return;
    int mid = l + r >> 1;
    build(lc[rt], l, mid);
    build(rc[rt], mid + 1, r);
}

void update(int &rt, int pre, int l, int r, int x){
    rt = ++cnt, lc[rt] = lc[pre], rc[rt] = rc[pre], sum[rt] = sum[pre] + 1;
    if(l == r) return;
    int mid = l + r >> 1;
    if(x <= mid) update(lc[rt], lc[pre], l, mid, x);
    else update(rc[rt], rc[pre], mid + 1, r, x);
}

int query(int L, int R, int l, int r, int k){
    if(l == r) return sum[R] - sum[L];
    int mid = l + r >> 1, ans = 0;
    if(k <= mid) ans += query(lc[L], lc[R], l, mid, k) + sum[rc[R]] - sum[rc[L]];
    else ans += query(rc[L], rc[R], mid + 1, r, k);
    return ans;
}

signed main(){
    int n = 0;
    n = read();
    for(int i = 1; i <= n; i++){
        a[i] = read();  //cin >> a[i];
        if(head[a[i]]) nxt[head[a[i]]] = i;
        head[a[i]] = i;
    }
    for(int i = 1; i <= n; i++)
        if(!nxt[i]) nxt[i] = n + 1;
    
    build(root[0], 1, n + 1);
    for(int i = 1; i <= n; i++) update(root[i], root[i - 1], 1, n + 1, nxt[i]);

    int m = read();
    while(m--){
        int l = read(), r = read();
        printf("%d\n", query(root[l - 1], root[r], 1, n + 1, r + 1));
    }
    return 0;
}

四、求区间小于等于$K$的数字个数(二分查询)

建立权值数组，对每个节点维护一颗主席树。查询为单点查询，查询数字对应的权值数组的个数。然后对于每个询问，我们在区间内二分枚举所有可能的数字$k$，然后查询区间第$k$小。反复查询求得一个满足$k\le h$的最大$k$。那么这个$k$就是我们想要得到的答案。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5 + 10;

ll root[N], sum[N << 5], lc[N << 5], rc[N << 5], tot = 0;
ll a[N], b[N];

inline void update(ll &rt, ll pre, ll l, ll r, ll k){
    rt = ++tot, lc[rt] = lc[pre], rc[rt] = rc[pre], sum[rt] = sum[pre] + 1;
    ll mid = l + r >> 1;
    if(l == r) return;
    if(k <= mid) update(lc[rt], lc[pre], l, mid, k);
    else update(rc[rt], rc[pre], mid + 1, r, k);
}

ll query(ll u, ll v, ll L, ll R, ll k){
    if(L == R) return L;
    ll mid = L + R >> 1;
    ll res = sum[lc[v]] - sum[lc[u]];
    if(res >= k) return query(lc[u], lc[v], L, mid, k);
    else return query(rc[u], rc[v], mid + 1, R, k - res);
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 0, T = 0; cin >> t;
    while(t--){
        ll n, m; cin >> n >> m;
        for(int i = 1; i <= n; i++){
            cin >> a[i]; b[i] = a[i];
        }
        sort(b + 1, b + 1 + n);
        ll sz = unique(b + 1, b + 1 + n) - b - 1;
        for(int i = 1; i <= n; i++){
            ll x = lower_bound(b + 1, b + 1 + sz, a[i]) - b;
            update(root[i], root[i - 1], 1, sz, x);
        }
        cout << "Case " << ++T << ":" << endl;
        while(m--){
            ll u, v, k; cin >> u >> v >> k;
            u++, v++;
            ll ans = 0, L = 0, R = v - u + 1;
            while(L < R){
                ll mid = (L + R + 1) >> 1;
                ll t = query(root[u - 1], root[v], 1, sz, mid);
                if(b[t] <= k) L = mid;
                else R = mid - 1;
            }
            cout << L << endl;
        }
    }
    return 0;
}

五、求区间Mex

给定$n$长度的数组， { a 1 , a 2 , . . . , a n } \{a_1, a_2,...,a_n\} {a1?,a2?,...,an?}，以及$m$次询问，每次给出一个数对$(l,r)$表示区间起点终点，要求对于给定的询问，回答在该区间内最小未出现的数字。

建立权值数组，对于每个点建立一棵主席树，维护权值最后一次出现的位置，那么对于查询$[l,r]$就是查找第$r$棵树上出现位置小于$l$的权值，那么只需要维护最后一次出现位置的最小值即可。

主席树解决该问题属于在线算法。这种题目可以用莫队强制离线处理。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int tot, root[N], tree[N << 5], lc[N << 5], rc[N << 5];

void update(int &rt, int pre, int l, int r, int x, int val){
    rt = ++tot, lc[rt] = lc[pre], rc[rt] = rc[pre];
    if(l == r){
        tree[rt] = val; 
        return;
    }
    int mid = l + r >> 1;
    if(x <= mid) update(lc[rt], lc[pre], l, mid, x, val);
    else update(rc[rt], rc[pre], mid + 1, r, x, val);
    tree[rt] = min(tree[lc[rt]], tree[rc[rt]]);
}

int query(int rt, int ql, int l, int r){
    if(l == r) return l;
    int mid = l + r >> 1;
    if(tree[lc[rt]] < ql) return query(lc[rt], ql, l, mid);
    else return query(rc[rt], ql, mid + 1, r);
}


signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m; cin >> n >> m;
    for(int i = 1, x; i <= n; i++){
        cin >> x; x++;
        if(x > n) root[i] = root[i - 1];
        else update(root[i], root[i - 1], 1, n + 1, x, i);
    }
    while(m--){
        int l, r; cin >> l >> r;
        cout << query(root[r], l, 1, n + 1) - 1 << endl;
    }
    return 0;
}

六、求区间内出现次数大于>=k次的最前数

对于给定的序列，输出待查询区间内出现次数严格大于区间长度一半的数字。

**思路：**考虑对查询过程进行剪枝，排除非法子树，向合法子树搜索。

首先考虑非法状态：因为对于主席树上任意一个节点，其代表的意义是管辖区间内数字的个数。因此对于主席树上某个节点，如果其代表区间数字的数目比区间长度的一半(也就是$\frac{r?l+1}{2}$)要小，那么子区间不回再出现满足该条件的数，在这种情况下可以直接返回$0$。

剩下的部分就是查询的板子。非法状态实际上就是在对查询过程进行剪枝。

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;

int a[N], b[N];
int tot, root[N << 5], sum[N << 5], lc[N << 5], rc[N << 5];

void update(int &rt, int pre, int l, int r, int v){
    rt = ++tot, lc[rt] = lc[pre], rc[rt] = rc[pre], sum[rt] = sum[pre] + 1;
    if(l == r) return;
    int mid = l + r >> 1;
    if(v <= mid) update(lc[rt], lc[pre], l, mid, v);
    else update(rc[rt], rc[pre], mid + 1, r, v);
}

int query(int L, int R, int l, int r, int k){
    if(sum[R] - sum[L] <= k) return 0;
    if(l == r) return l;
    int now = sum[lc[R]] - sum[lc[L]], mid = l + r >> 1;
    if(now > k) return query(lc[L], lc[R], l, mid, k);
    else return query(rc[L], rc[R], mid + 1, r, k);
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, q; cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    int m = unique(b + 1, b + n + 1) - b - 1;
    for(int i = 1; i <= n; i++){
        int x = lower_bound(b + 1, b + m + 1, a[i]) - b;
        update(root[i], root[i - 1], 1, m, x);
    }
    while(q--){
        int l, r; cin >> l >> r;
        int k = (r - l + 1) >> 1;
        cout << b[query(root[l - 1], root[r], 1, m, k)] << endl;
    }
    return 0;
}

七、主席树+树上路径

给定一棵 $n$ 个节点的树，每个点有一个权值。有 $m$ 个询问，每次给你 $u,v,k$ 你需要回答 $u\text{?xor?last}$ 和 $v$ 这两个节点间第 $k$ 小的点权。

动态查询树上区间点权第$k$小，且查询之间具有关系，因此考虑建立主席树维护区间信息。

首先回顾主席树维护线性区间第$k$大/小时我们的处理思路：

对于全局区间第$k$小时，我们建立全局权值线段树，维护的区间和表示某点子树中点的个数。那么我们在寻找区间第$k$小时，只需要左右二分寻找即可。而对于某个区间的第$k$小，一个朴素的方式便是我们每次都建立一颗线段树，但显然这样是不明智的算法。那么我们是如何查询这个区间第$k$小的呢？

对于这个维护的过程我们很容易联想到前缀和的概念，我们可以先离线建树，对于每个点建立一棵主席树，维护$[1,i]$区间，那么对于区间查询$[l,r]$时，我们只需要查询到区间$[1,l?1]$和$[1,r]$即可取得区间的信息，实现区间查询。

然后分析样例，作出样例所示的树(假设以$1$为根节点)：

那么我们可以发现，对于树上区间查询，我们也可以利用类似于线性区间查询的思路进行解决，但是由于树的结构限制，我们把线性区间的前缀和改为树上前缀和的形式：
$$query(u,v)=sum[u]+sum[v]?sum[lca(u,v)]?sum[fa[lca(u,v)]]$$
下面我们来说明这个式子：

如上，从根节点到$5$号节点的路径+从根节点到$7$号节点的路径重复了两次，那么我们要减去重叠的信息：对于根节点到交点父节点的信息均重复两次，到交点的信息重复一次(因为交点在链上，需要保留一次信息)，因此前缀和形式便是$sum[u]+sum[v]?sum[lca(u,v)]?sum[fa[lca(u,v)]]$。

#include <bits/stdc++.h>
#define id(x) (lower_bound(b + 1, b + le + 1, a[x]) - b)
#define rid(x) (b[x])
using namespace std;

const int N = 1e5 + 10;

int n, m, le, ans = 0, lastans = 0;
int a[N], b[N], f[N][19], dep[N];
vector<int> g[N];

struct node{ int sum, lc, rc; }tree[N << 5];
int root[N], cnt = 0;


void build(node &rt, int l, int r){
    rt.sum = 0;
    if(l == r) return;
    int mid = l + r >> 1;
    build(tree[rt.lc = ++cnt], l, mid);
    build(tree[rt.rc = ++cnt], mid + 1, r);
}

inline void update(node pre, node &rt, int l, int r, int p){
    rt.sum = pre.sum + 1;
    if(l == r) return;
    int mid = l + r >> 1;
    if(p <= mid) update(tree[pre.lc], tree[rt.lc = ++cnt], l, mid, p), rt.rc= pre.rc;
    else update(tree[pre.rc], tree[rt.rc = ++cnt], mid + 1, r, p), rt.lc = pre.lc;
}

inline int query(node u, node v, node lca, node lca_fa, int l, int r, int k){
    if(l == r) return l;
    int sum = tree[u.lc].sum + tree[v.lc].sum - tree[lca.lc].sum - tree[lca_fa.lc].sum;
    int mid = l + r >> 1;
    if(sum >= k) return query(tree[u.lc], tree[v.lc], tree[lca.lc], tree[lca_fa.lc], l, mid, k);
    return query(tree[u.rc], tree[v.rc], tree[lca.rc], tree[lca_fa.rc], mid + 1, r, k - sum);
}

inline void dfs(int u, int fa){
    update(tree[root[fa]], tree[root[u] = ++cnt], 1, le, id(u));
    f[u][0] = fa;
    dep[u] = dep[fa] + 1;
    for(register int i = 1; i <= 18; i++) f[u][i] = f[f[u][i - 1]][i - 1];
    for(auto v : g[u]){
        if(v == fa) continue;
        dfs(v, u);
    }
}

inline int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    for(register int i = 18; i >= 0; i--)
        if(dep[f[u][i]] >= dep[v]) u = f[u][i];
    if(u == v) return u;
    for(register int i = 18; i >= 0; i--)
        if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    return f[u][0];
}

inline int querypath(int u, int v, int k){
    int lcaa = lca(u, v);
    return rid(query(tree[root[u]], tree[root[v]], tree[root[lcaa]], tree[root[f[lcaa][0]]], 1, le, k));
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    //freopen("stdin.in", "r", stdin);
    //freopen("stdout.out", "w", stdout);
    cin >> n >> m;
    for(register int i = 1; i <= n; i++){ cin >> a[i]; b[i] = a[i]; }
    for(register int i = 1, u, v; i < n; i++){
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    sort(b + 1, b + 1 + n);
    le = unique(b + 1, b + n + 1) - (b + 1);
    build(tree[root[0] = ++cnt], 1, le);
    dfs(1, 0);
    while(m--){
        int u, v, k; cin >> u >> v >> k;
        ans = querypath(u ^ lastans, v, k);
        cout << ans << endl;
        lastans = ans;
    }
    return 0;
}

ster int i = 1; i <= n; i++){ cin >> a[i]; b[i] = a[i]; }
for(register int i = 1, u, v; i < n; i++){
cin >> u >> v;
g[u].push_back(v), g[v].push_back(u);
}
sort(b + 1, b + 1 + n);
le = unique(b + 1, b + n + 1) - (b + 1);
build(tree[root[0] = ++cnt], 1, le);
dfs(1, 0);
while(m–){
int u, v, k; cin >> u >> v >> k;
ans = querypath(u ^ lastans, v, k);
cout << ans << endl;
lastans = ans;
}
return 0;
}