Wiki › Tham khảo ngôn ngữ › Policy-Based Data Structures (PBDS) trong C++

Policy-Based Data Structures (PBDS) trong C++

Thư viện pb_ds của GCC: ordered_set với find_by_order và order_of_key, multiset bằng cặp (giá trị, id), gp_hash_table chống hack, priority_queue có join và modify, rope; kèm phương án thay thế trong Python.

huunguyen huunguyen Updated Tháng 11. 17, 2026 Đọc 24 phút 4 lượt xem

Policy-Based Data Structures (PBDS, thư viện pb_ds của GCC) là bộ cấu trúc dữ liệu "có sẵn" đi kèm trình biên dịch GCC, không thuộc chuẩn C++ nhưng dùng được trên hầu hết các judge. Món quý nhất là cây thống kê thứ tự (order statistics tree): một std::set biết thêm hai phép tìm phần tử nhỏ thứ k và đếm số phần tử nhỏ hơn x, cả hai trong O(logN), trong khi std::set phải duyệt tuần tự mất O(N). Ngoài ra pb_ds còn có bảng băm gp_hash_table nhanh hơn unordered_map, hàng đợi ưu tiên hỗ trợ gộp (join) và sửa khoá (modify), và rope cho phép cắt dán đoạn của dãy trong O(logN). Trang này là bản tra cứu nhanh kèm các bẫy thường gặp; phần STL chuẩn xem ở C++ STL Cheatsheet.

Ý tưởng / Trực giác

Vì sao std::set không trả lời được "phần tử thứ k"?

std::set là cây đỏ đen: mỗi nút chỉ biết khoá của mình và hai con. Muốn biết "khoá x đứng thứ mấy", cây phải đếm số nút bên trái x, và không có thông tin nào giúp đếm nhanh, nên distance(s.begin(), it) tốn O(N).

Cách sửa rất tự nhiên: mỗi nút lưu thêm kích thước cây con của nó. Khi đó tại một nút v có cây con trái kích thước L:

  • nếu k<L: phần tử thứ k (đếm từ 0) nằm trong cây con trái, đi xuống trái;
  • nếu k=L: chính là v;
  • nếu k>L: đi xuống phải với k←k−L−1.

Mỗi bước xuống một tầng, cây đỏ đen cao O(logN), nên tìm phần tử thứ k tốn O(logN). Đếm số phần tử nhỏ hơn x làm ngược lại: đi từ gốc tìm x, mỗi lần rẽ phải thì cộng kích thước cây con trái cộng 1. Kích thước cây con chỉ thay đổi trên đường từ nút bị chèn/xoá lên gốc và ở các nút bị xoay, nên vẫn cập nhật được trong O(logN).

pb_ds cài sẵn đúng ý tưởng này dưới tên chính sách cập nhật nút tree_order_statistics_node_update. Chữ "policy-based" nghĩa là: ta ghép cấu trúc từ các "chính sách" (kiểu cây, hàm so sánh, dữ liệu phụ lưu ở nút) thay vì viết lại từ đầu. Đây cũng chính là "cây BST có lưu size" trong Treap, chỉ khác là GCC cài hộ ta.

Ba công cụ còn lại
  • gp_hash_table: bảng băm địa chỉ mở (open addressing), dò tuyến tính trên mảng liên tục nên ít cấp phát bộ nhớ và thân thiện cache hơn unordered_map (mỗi phần tử là một nút danh sách liên kết riêng). Thường nhanh hơn khoảng 2 đến 3 lần. Lý thuyết bảng băm xem Bảng băm.
  • __gnu_pbds::priority_queue: mặc định là pairing heap. Khác std::priority_queue, nó trả về một "tay cầm" (point_iterator) cho mỗi phần tử, nhờ đó ta sửa khoá hoặc xoá một phần tử bất kỳ, và gộp hai heap trong O(1).
  • __gnu_cxx::rope: dãy biểu diễn bằng cây, chèn/xoá/cắt một đoạn ở giữa dãy trong O(logN) thay vì O(N) như vector.

Ví dụ chạy tay

Cây thống kê thứ tự: find_by_order và order_of_key

Chèn lần lượt 5,1,8,3,9 vào ordered_set. Tập luôn được giữ có thứ tự, ta hình dung nó như một mảng đã sắp xếp đánh số từ 0:

array base=0
1 3 5 8 9
step find_by_order(2): phần tử ở vị trí 2 (nhỏ thứ ba) là 5
highlight green 2
step order_of_key(6): các phần tử nhỏ hơn 6 là 1, 3, 5, trả về 3
clear
highlight orange 0..2
step order_of_key(5): chỉ đếm phần tử NHỎ HƠN HẲN 5, trả về 2
clear
highlight orange 0..1
highlight red 2
Lệnh Kết quả Giải thích
*s.find_by_order(0) 1 phần tử nhỏ nhất
*s.find_by_order(2) 5 nhỏ thứ ba (đếm từ 0)
s.find_by_order(5) == s.end() true k≥ size trả về end()
s.order_of_key(6) 3 số phần tử <6
s.order_of_key(5) 2 so sánh ngặt, 5 không được đếm
s.erase(3) rồi *s.find_by_order(1) 5 tập còn {1,5,8,9}
Multiset bằng cặp (giá trị, chỉ số)

ordered_set không chứa được hai phần tử bằng nhau. Mẹo chuẩn: lưu cặp (x,id) với id là số thứ tự chèn, khác nhau cho mọi lần chèn. Các cặp không bao giờ trùng, và sắp theo cặp thì vẫn sắp theo x trước. Xét chuỗi thao tác:

+ 5   + 2   + 5   + 8   ? 3   # 5   - 5   ? 3   ? 4

(+ x: chèn, - x: xoá một bản sao, ? k: phần tử nhỏ thứ k đếm từ 1, # x: số phần tử <x.)

array base=0
(2,1) (5,0) (5,2) (8,3)
step Sau 4 lần chèn: id lần lượt là 0, 1, 2, 3
step ? 3: find_by_order(2) là cặp (5,2), in 5
highlight green 2
step # 5: order_of_key((5, INT_MIN)) đếm các cặp nhỏ hơn (5, -vô cùng), chỉ có (2,1), in 1
clear
highlight orange 0
step - 5: lower_bound((5, INT_MIN)) trỏ tới (5,0), xoá đúng một bản sao
clear
highlight red 1

Sau khi xoá, tập là {(2,1),(5,2),(8,3)}: ? 3 in 8, ? 4 in −1 (không tồn tại). Toàn bộ output là 5 1 8 -1, khớp với chương trình ở phần Cài đặt.

Điểm mấu chốt: muốn "đếm số phần tử <x" thì truy vấn order_of_key({x, INT_MIN}); muốn "đếm số phần tử ≤x" thì order_of_key({x, INT_MAX}).

Đếm nghịch thế online

Dãy a=[4,2,4,1,3]. Duyệt từ trái sang phải; trước khi chèn aj, số phần tử đã gặp lớn hơn aj bằng j−(số phần tử≤aj):

array
4 2 4 1 3
step j=1, a=4: chưa có gì, cộng 0
highlight blue 1
step j=2, a=2: đã có {4}, số phần tử lớn hơn 2 là 1
highlight orange 1
highlight blue 2
step j=3, a=4: đã có {2, 4}, phần tử bằng 4 KHÔNG tính, cộng 0
clear
highlight blue 3
step j=4, a=1: đã có {2, 4, 4}, cả 3 đều lớn hơn 1, cộng 3
clear
highlight orange 1..3
highlight blue 4
step j=5, a=3: đã có {1, 2, 4, 4}, hai số 4 lớn hơn 3, cộng 2
clear
highlight orange 1 3
highlight blue 5
j aj đã gặp (đã sắp) số phần tử ≤aj cộng thêm
1 4 {} 0 0
2 2 {4} 0 1
3 4 {2,4} 2 0
4 1 {2,4,4} 0 3
5 3 {1,2,4,4} 2 2

Tổng: 0+1+0+3+2=6 nghịch thế: (4,2),(4,1),(4,3),(2,1),(4,1),(4,3).

Cài đặt

Khai báo ordered_set và ordered_map
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// ordered_set: like std::set, plus find_by_order and order_of_key
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
                         tree_order_statistics_node_update>;

// ordered_map: like std::map; find_by_order returns an iterator to (key, value)
template <class K, class V>
using ordered_map = tree<K, V, less<K>, rb_tree_tag,
                         tree_order_statistics_node_update>;

int main() {
    ordered_set<int> s;
    for (int x : {5, 1, 8, 3, 9}) s.insert(x);   // s = {1, 3, 5, 8, 9}
    cout << *s.find_by_order(2) << '\n';          // 5
    cout << s.order_of_key(6) << '\n';            // 3

    ordered_map<string, int> score;
    score["dung"] = 7;
    score["an"] = 9;
    score["binh"] = 4;
    auto it = score.find_by_order(1);             // 2nd key in sorted order
    cout << it->first << ' ' << it->second << '\n';  // binh 4
    cout << score.order_of_key("c") << '\n';      // 2 (an, binh)
}

Ý nghĩa các tham số của tree<Key, Mapped, Cmp, Tag, NodeUpdate>:

Tham số Giá trị thường dùng Ý nghĩa
Key int, pair<int,int> kiểu khoá
Mapped null_type hoặc V null_type cho set, kiểu giá trị cho map
Cmp less<Key> hàm so sánh; greater<Key> để sắp giảm dần
Tag rb_tree_tag cây đỏ đen (còn splay_tree_tag, ov_tree_tag nhưng chậm hơn)
NodeUpdate tree_order_statistics_node_update dữ liệu phụ ở nút; đây là thứ bật find_by_order

Mọi hàm quen thuộc của std::set vẫn có: insert, erase (theo khoá hoặc iterator), find, lower_bound, upper_bound, begin, end, size, duyệt bằng for.

Multiset với k-th element online

Chương trình đọc q thao tác + x, - x, ? k, # x như ví dụ chạy tay. Bản Python dùng Fenwick Tree trên giá trị đã nén toạ độ, vì Python không có pb_ds (xem mục Python bên dưới).

C++
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// multiset of ints: each element is (value, unique id)
using ordered_multiset = tree<pair<int, int>, null_type, less<pair<int, int>>,
                              rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    ordered_multiset s;
    int nextId = 0;
    while (q--) {
        char op;
        int x;
        cin >> op >> x;
        if (op == '+') {                    // insert one copy of x
            s.insert({x, nextId++});
        } else if (op == '-') {             // erase ONE copy of x (if any)
            auto it = s.lower_bound({x, INT_MIN});
            if (it != s.end() && it->first == x) s.erase(it);
        } else if (op == '?') {             // x-th smallest, 1-indexed
            if (x < 1 || x > (int)s.size()) cout << -1 << '\n';
            else cout << s.find_by_order(x - 1)->first << '\n';
        } else {                            // '#': how many elements < x
            cout << s.order_of_key({x, INT_MIN}) << '\n';
        }
    }
}
Python
import sys


class FenwickOrderedMultiset:
    """Multiset over values known in advance (offline compression)."""

    def __init__(self, values):
        self.vals = sorted(set(values))
        self.idx = {v: i + 1 for i, v in enumerate(self.vals)}
        self.n = len(self.vals)
        self.bit = [0] * (self.n + 1)
        self.cnt = [0] * (self.n + 1)
        self.size = 0
        self.log = max(1, self.n.bit_length())

    def _add(self, i, d):
        while i <= self.n:
            self.bit[i] += d
            i += i & -i

    def insert(self, v):
        i = self.idx[v]
        self.cnt[i] += 1
        self.size += 1
        self._add(i, 1)

    def erase_one(self, v):
        i = self.idx.get(v)
        if i is not None and self.cnt[i] > 0:
            self.cnt[i] -= 1
            self.size -= 1
            self._add(i, -1)

    def count_less(self, v):
        # number of elements < v: prefix sum up to the largest rank with value < v
        lo, hi = 0, self.n
        while lo < hi:  # first rank whose value >= v
            mid = (lo + hi) // 2
            if self.vals[mid] < v:
                lo = mid + 1
            else:
                hi = mid
        i, s = lo, 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def kth(self, k):
        # k-th smallest (1-indexed) by binary lifting on the Fenwick tree
        pos = 0
        for b in range(self.log, -1, -1):
            nxt = pos + (1 << b)
            if nxt <= self.n and self.bit[nxt] < k:
                pos = nxt
                k -= self.bit[nxt]
        return self.vals[pos]  # rank pos + 1 has index pos in vals


def main():
    data = sys.stdin.buffer.read().split()
    q = int(data[0])
    ops = [(data[1 + 2 * i].decode(), int(data[2 + 2 * i])) for i in range(q)]
    ms = FenwickOrderedMultiset([x for op, x in ops if op == '+'])
    out = []
    for op, x in ops:
        if op == '+':
            ms.insert(x)
        elif op == '-':
            ms.erase_one(x)
        elif op == '?':
            out.append(ms.kth(x) if 1 <= x <= ms.size else -1)
        else:
            out.append(ms.count_less(x))
    print("\n".join(map(str, out)))


main()

Input (đúng ví dụ chạy tay):

9
+ 5
+ 2
+ 5
+ 8
? 3
# 5
- 5
? 3
? 4

Output của cả hai chương trình:

5
1
8
-1
Đếm nghịch thế
C++
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// multiset emulation: store (value, unique index) so equal values never collide
using ordered_multiset = tree<pair<int, int>, null_type, less<pair<int, int>>,
                              rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    int n;
    cin >> n;
    ordered_multiset s;
    long long inversions = 0;
    for (int j = 0; j < n; j++) {
        int x;
        cin >> x;
        // elements seen so far that are <= x: all pairs (v, i) < (x, INT_MAX)
        int notGreater = s.order_of_key({x, INT_MAX});
        inversions += (long long)s.size() - notGreater;  // previous elements > x
        s.insert({x, j});
    }
    cout << inversions << '\n';
}
Python
import sys
from bisect import bisect_left


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))
    # coordinate compression: value -> rank in 1..m
    vals = sorted(set(a))
    m = len(vals)
    bit = [0] * (m + 1)  # Fenwick tree over ranks, bit counts how many seen

    def add(i):
        while i <= m:
            bit[i] += 1
            i += i & -i

    def prefix(i):  # number of seen elements with rank <= i
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    inversions = 0
    for j, x in enumerate(a):
        r = bisect_left(vals, x) + 1
        inversions += j - prefix(r)  # previous elements with value > x
        add(r)
    print(inversions)


main()

Với input 5 / 4 2 4 1 3, cả hai in 6. Bài này chỉ cần đếm nên Fenwick (cả C++) vừa nhanh vừa ít bộ nhớ hơn; ordered_set thắng khi giá trị không biết trước (không nén offline được) hoặc cần cả find_by_order.

gp_hash_table với hàm băm chống hack
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

// splitmix64 with a random seed chosen at runtime: anti-hack hash
struct SplitMix64Hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t SEED =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + SEED);
    }
};

int main() {
    gp_hash_table<long long, int, SplitMix64Hash> cnt;  // open addressing
    for (long long x : {7LL, 1000000000000LL, 7LL, -3LL, 7LL}) cnt[x]++;
    cout << cnt[7] << ' ' << cnt[-3] << ' ' << cnt.size() << '\n';  // 3 1 3
    cout << (cnt.find(42) == cnt.end()) << '\n';                   // 1
    cc_hash_table<int, int, SplitMix64Hash> other;  // chaining variant, same API
    other[5] = 10;
    cout << other[5] << '\n';                                      // 10
}

Vì sao cần hàm băm riêng: hàm băm mặc định của số nguyên là hàm đồng nhất (h(x)=x), còn gp_hash_table dùng kích thước bảng là luỹ thừa của 2 và lấy các bit thấp. Chỉ cần cho toàn khoá là bội của 216 là mọi khoá rơi vào cùng một ô, mỗi thao tác thành O(N). Trộn bit bằng splitmix64 với seed ngẫu nhiên lúc chạy khiến người ra test không thể biết trước khoá nào va chạm (cùng ý tưởng với Thuật toán ngẫu nhiên). Lưu ý gp_hash_table không có count; dùng find(x) != end().

Hàng đợi ưu tiên có join và modify
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using MaxHeap = __gnu_pbds::priority_queue<int>;  // default: max-heap, pairing_heap_tag

int main() {
    MaxHeap a, b;
    for (int x : {3, 9, 4}) a.push(x);
    for (int x : {7, 1}) b.push(x);
    a.join(b);  // move all of b into a, b becomes empty
    cout << a.size() << ' ' << b.size() << ' ' << a.top() << '\n';  // 5 0 9
    auto it = a.push(2);
    a.modify(it, 100);  // change a value through its point_iterator
    cout << a.top() << '\n';  // 100
    a.erase(it);              // erase an arbitrary element
    cout << a.top() << '\n';  // 9
}

join dùng cho bài gộp heap (mergeable heap): ví dụ gộp tập của các con lên cha trên cây, hoặc gộp hai nhóm khi hai thành phần DSU hợp lại. Với std::priority_queue ta phải gộp nhỏ vào lớn (O(Nlog2N) tổng), còn pairing heap gộp trong O(1).

modify cho phép Dijkstra với decrease-key: mỗi đỉnh chỉ có tối đa một nút trong heap, không có "bản ghi cũ" phải bỏ qua. Đồ thị ví dụ (vô hướng, nguồn là đỉnh 1):

graph weighted
5 6
1 2 4
1 3 1
3 2 2
2 4 5
3 4 8
4 5 3
path green 1 3 2 4 5
Bước Lấy ra Thao tác trên heap
1 (0,1) push (4,2), push (1,3)
2 (1,3) 1+2=3<4: modify đỉnh 2 thành (3,2); push (9,4)
3 (3,2) 3+5=8<9: modify đỉnh 4 thành (8,4)
4 (8,4) push (11,5)
5 (11,5) heap rỗng, dừng

Khoảng cách: 0 3 1 8 11.

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;

using ll = long long;
// min-heap by distance: greater<> on pair (dist, vertex)
using Heap = __gnu_pbds::priority_queue<pair<ll, int>, greater<pair<ll, int>>,
                                        __gnu_pbds::pairing_heap_tag>;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    const ll INF = LLONG_MAX;
    vector<ll> dist(n + 1, INF);
    vector<Heap::point_iterator> where(n + 1);  // handle to v's node in heap
    vector<bool> inHeap(n + 1, false);
    Heap pq;
    dist[1] = 0;
    where[1] = pq.push({0, 1});
    inHeap[1] = true;
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        inHeap[u] = false;
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                if (inHeap[v]) {
                    pq.modify(where[v], {dist[v], v});  // decrease-key in place
                } else {
                    where[v] = pq.push({dist[v], v});
                    inHeap[v] = true;
                }
            }
        }
    }
    // each vertex enters the heap at most once (no stale entries)
    for (int v = 1; v <= n; v++) cout << (dist[v] == INF ? -1 : dist[v]) << " \n"[v == n];
}

Thực tế bản Dijkstra thông thường với std::priority_queue và "bỏ qua bản ghi cũ" thường nhanh ngang hoặc nhanh hơn, vì std::priority_queue là mảng liên tục. Decrease-key đáng dùng khi bộ nhớ chật (heap chỉ O(N) thay vì O(M)) hoặc khi đồ thị rất dày.

Custom node update (tóm tắt)

tree_order_statistics_node_update chỉ là một chính sách lưu "kích thước cây con". Ta tự viết được chính sách khác, ví dụ lưu tổng khoá trong cây con để trả lời "tổng các phần tử <x" trong O(logN):

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// Custom node update: every node stores the sum of keys in its subtree.
template <class NodeCItr, class NodeItr, class Cmp, class Alloc>
struct sum_update {
    typedef long long metadata_type;  // extra data stored in each node

    // called bottom-up whenever node 'it' changes; recompute from children
    void operator()(NodeItr it, NodeCItr endIt) {
        NodeItr l = it.get_l_child(), r = it.get_r_child();
        long long s = **it;  // key of this node (for a set, **it is the key)
        if (l != endIt) s += l.get_metadata();
        if (r != endIt) s += r.get_metadata();
        const_cast<long long&>(it.get_metadata()) = s;
    }

    // sum of keys strictly less than x: walk down from the root
    long long prefix_sum(int x) {
        long long res = 0;
        NodeCItr it = node_begin();
        while (it != node_end()) {
            NodeCItr l = it.get_l_child();
            if (**it < x) {
                res += **it;
                if (l != node_end()) res += l.get_metadata();
                it = it.get_r_child();
            } else {
                it = l;
            }
        }
        return res;
    }

    virtual NodeCItr node_begin() const = 0;
    virtual NodeCItr node_end() const = 0;
    virtual ~sum_update() {}
};

int main() {
    tree<int, null_type, less<int>, rb_tree_tag, sum_update> s;
    for (int x : {5, 1, 8, 3, 9}) s.insert(x);
    cout << s.prefix_sum(6) << '\n';   // 1 + 3 + 5 = 9
    s.erase(3);
    cout << s.prefix_sum(100) << '\n'; // 1 + 5 + 8 + 9 = 23
}

Cú pháp khá rườm rà; khi cần dữ liệu phụ phức tạp hơn (cộng lazy, đảo đoạn), tự cài Treap thường dễ kiểm soát hơn.

rope (tóm tắt)
#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;

int main() {
    rope<int> r;
    for (int i = 1; i <= 6; i++) r.push_back(i);  // 1 2 3 4 5 6
    // cut the block [1, 3) (values 2 3) and paste it at the end
    rope<int> block = r.substr(1, 2);
    r.erase(1, 2);                    // 1 4 5 6
    r.insert(r.size(), block);        // 1 4 5 6 2 3
    for (int x : r) cout << x << ' ';
    cout << '\n';
    cout << r[4] << '\n';             // 2 (random access by position)
}

Output: 1 4 5 6 2 3 rồi 2. rope hợp với bài "cắt một đoạn dán sang chỗ khác" hoặc lưu nhiều phiên bản (sao chép rope tốn O(1) vì chia sẻ nút). Hằng số lớn và không hỗ trợ đảo đoạn hay truy vấn tổng; bài có các thao tác đó nên dùng treap ngầm định.

Python: không có pb_ds

Python không có cây thống kê thứ tự trong thư viện chuẩn, và sortedcontainers thường không được cài trên judge. Hai lựa chọn:

  • Fenwick trên giá trị nén (như lớp FenwickOrderedMultiset ở trên): nhanh, O(logN) mỗi thao tác, nhưng cần biết trước mọi giá trị (đọc hết input rồi nén).
  • List đã sắp + bisect: đơn giản nhất, hợp với N cỡ 105 vì insort và pop dịch mảng bằng memmove rất nhanh dù về lý thuyết là O(N).
from bisect import bisect_left, insort

a = []                      # always kept sorted
for x in [5, 2, 5, 8]:
    insort(a, x)            # O(n) shift, but a fast memmove
print(a[3 - 1])             # 3rd smallest: 5
print(bisect_left(a, 5))    # count of elements < 5: 1
a.pop(bisect_left(a, 5))    # erase one copy of 5
print(a)                    # [2, 5, 8]

Hàng đợi ưu tiên trong Python là heapq (không có join/modify), bảng băm là dict. Xem thêm Python cho lập trình thi đấu.

Độ phức tạp

Cấu trúc Thao tác Thời gian Ghi chú
tree (rb_tree_tag) insert, erase, find, lower_bound O(logN) như std::set
find_by_order, order_of_key O(logN) đi một đường từ gốc xuống lá
gp_hash_table [], find, insert, erase O(1) trung bình xấu nhất O(N) nếu bị hack hàm băm
priority_queue (pairing heap) push, top, join O(1)
pop, erase O(logN) khấu hao
modify O(logN) khấu hao giảm khoá thực tế rất nhanh
rope insert, erase, substr ở giữa O(logN) hằng số lớn
r[i] O(logN) không phải O(1) như vector

Lý giải: cây đỏ đen cao không quá 2log2(N+1); mỗi nút lưu thêm kích thước cây con, giá trị này chỉ đổi ở các nút trên đường chèn/xoá và các nút bị xoay (tối đa O(logN) nút), nên find_by_order và order_of_key chỉ cần một lượt đi xuống. Pairing heap gộp hai heap bằng cách gắn gốc nhỏ hơn làm con gốc kia (O(1)), độ phức tạp pop là khấu hao.

Bộ nhớ: tất cả O(N). Tuy nhiên mỗi nút của tree gồm khoá, ba con trỏ (cha, trái, phải), màu và metadata: với pair<int,int> một nút chiếm 48 byte (đo bằng sizeof trên GCC 14, chưa kể phần quản lý của bộ cấp phát), nên 106 phần tử tốn cỡ 50 đến 64 MB. gp_hash_table cấp phát bảng gấp đôi lên khi đầy nên có lúc dùng gấp vài lần số phần tử.

⚠️ Lỗi thường gặp

  • Dùng less_equal để làm multiset. Nhiều tài liệu khuyên tree<int, null_type, less_equal<int>, ...> để chứa phần tử trùng. Triệu chứng: find(x) luôn trả về end(), erase(x) âm thầm không xoá gì, còn lower_bound và upper_bound bị đổi vai cho nhau. Đã kiểm tra trên GCC 14: chèn {2,2,5} rồi erase(2) thì size vẫn là 3, *lower_bound(2) ra 5. Lý do: less_equal không phải thứ tự ngặt, cây không bao giờ thấy hai khoá "bằng nhau" (!cmp(a,b) && !cmp(b,a) không bao giờ đúng). Cách tránh: dùng cặp (giá trị, id duy nhất) và xoá bằng iterator từ lower_bound({x, INT_MIN}).
  • Chỉ có trên GCC. pb_ds và rope là phần mở rộng của libstdc++: MSVC không có, Clang với libc++ (mặc định trên macOS) báo lỗi không tìm thấy header. Judge chạy GCC thì ổn; trên máy Mac cần cài g++ thật (Homebrew gcc), vì lệnh g++ mặc định thực chất là Clang.
  • find_by_order(k) với k≥ size trả về end(). Giải tham chiếu *s.find_by_order(k) lúc đó là hành vi không xác định (in rác hoặc crash). Luôn kiểm tra k < s.size(). Nhớ find_by_order đếm từ 0: phần tử nhỏ thứ k (đếm từ 1) là find_by_order(k - 1).
  • order_of_key trả về size_t không dấu. Viết s.order_of_key(x) - 1 khi kết quả là 0 sẽ tràn thành số khổng lồ. Ép sang int/long long trước khi trừ. Cũng nhớ order_of_key(x) đếm phần tử nhỏ hơn hẳn x; muốn ≤x thì dùng order_of_key(x + 1) (số nguyên) hoặc {x, INT_MAX} (với cặp).
  • Hằng số lớn, tưởng O(logN) là đủ. ordered_set chậm hơn std::set khoảng 1,5 đến 2 lần và chậm hơn Fenwick nhiều lần. Với N=106 thao tác trong 1 giây có thể TLE. Nếu giá trị biết trước (nén được offline), dùng Fenwick Tree với tìm kiếm nhị phân trên cây.
  • gp_hash_table với hàm băm mặc định bị hack. Trên Codeforces và các kỳ có hack, test toàn bội của luỹ thừa 2 làm mọi thao tác thành O(N), TLE. Luôn kèm hàm băm splitmix64 có seed ngẫu nhiên như trên. Với khoá là pair, tự gộp thành uint64_t rồi băm.
  • Quên rằng modify/erase cần point_iterator còn hợp lệ. Sau khi pop phần tử đó, tay cầm cũ không còn dùng được; gọi modify lên nó là hành vi không xác định. Theo dõi phần tử nào còn trong heap (như mảng inHeap ở bản Dijkstra).
  • using namespace __gnu_pbds; đè tên priority_queue. Khi đã using namespace std; và using namespace __gnu_pbds; thì priority_queue trở nên nhập nhằng, báo lỗi biên dịch. Hãy viết đầy đủ std::priority_queue hoặc __gnu_pbds::priority_queue.

Biến thể / Mở rộng

  • Sắp giảm dần: đổi less<T> thành greater<T>, khi đó find_by_order(0) là phần tử lớn nhất.
  • split và join của tree: s.split(x, t) chuyển mọi phần tử >x sang t; s.join(t) nối lại (dùng khi mọi khoá của t lớn hơn mọi khoá của s, đúng tình huống sau một lần split). Nhanh hơn nhiều so với chèn lại từng phần tử, hợp với bài tách/ghép tập theo ngưỡng giá trị.
  • Trung vị động: giữ tập bằng ordered_multiset, trung vị là find_by_order((size - 1) / 2). Cách khác không cần pb_ds là hai heap (xem Tham lam với heap và Heap).
  • Khi cần nhiều hơn: truy vấn theo đoạn chỉ số, cập nhật lazy, đảo đoạn thì dùng Segment Tree hoặc Treap. Phần tử nhỏ thứ k trên một đoạn con của mảng dùng Persistent Segment Tree hoặc Wavelet Tree.

Bài tập luyện

  • Trung vị (icpc22mbh) (Trung bình) Thêm, xoá một bản sao và hỏi trung vị online; luyện mẹo multiset bằng cặp (giá trị, id) cùng find_by_order.
  • Truy vấn giá (tnhsg1026_b) (Trung bình) Hỏi mức giá phân biệt nhỏ thứ k khi danh sách thay đổi; ordered_set các giá phân biệt kèm bộ đếm số lượng mỗi giá.
  • Trung Vị Cửa Sổ Trượt (swmedian) (Khó) Trung vị mọi cửa sổ độ dài k: mỗi bước chèn một phần tử, xoá một phần tử và gọi find_by_order.
  • Bắn bi (thhv23_marbles) (Khó) Tìm viên bi còn sống thứ bi rồi xoá nó; ordered_set các chỉ số còn sống thay cho Fenwick.
  • Xếp hạng lại (vtc03_rank) (Khó) Đếm nghịch thế và, với mỗi học sinh, số người cao hơn bên trái và thấp hơn bên phải bằng order_of_key; N=5·105 nên so sánh tốc độ với Fenwick.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0