Wiki › Thuật toán › Chặt nhị phân song song (Parallel Binary Search)

Chặt nhị phân song song (Parallel Binary Search)

Kỹ thuật offline chặt nhị phân cho mọi truy vấn cùng lúc, dùng chung một lượt mô phỏng mỗi vòng. Gồm hai cách cài: theo vòng (thời điểm sớm nhất thỏa điều kiện) và chia để trị trên đáp án (nhỏ thứ k có cập nhật).

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

Chặt nhị phân song song (parallel binary search) là kỹ thuật offline trả lời cùng lúc Q truy vấn, mà mỗi truy vấn riêng lẻ có thể giải bằng chặt nhị phân trên đáp án, nhưng việc kiểm tra "đáp án ≤mid?" lại cần mô phỏng cả một quá trình tốn kém (thêm dần cạnh vào DSU, áp dần các cập nhật lên mảng, ...). Chặt nhị phân riêng cho từng truy vấn tốn O(Q·logT·chi phí mô phỏng), quá chậm. Chặt nhị phân song song cho mọi truy vấn dùng chung một lần mô phỏng mỗi vòng, nên tổng chi phí chỉ còn O(logT·(chi phí mô phỏng+Q)).

Dạng bài nhận diện: "với mỗi truy vấn, tìm thời điểm sớm nhất mà một điều kiện đơn điệu được thỏa" (sau bao nhiêu thao tác thì u, v liên thông, sau bao nhiêu trận mưa thì quốc gia i gom đủ pi đơn vị, ...), hoặc "tìm phần tử nhỏ thứ k" trên một tập thay đổi theo thời gian. Giới hạn điển hình: N,Q,T≤105 đến 2·105.

Kỹ thuật có hai cách cài đặt tương đương:

  • Theo vòng: mỗi truy vấn giữ khoảng [loi,hii] của riêng nó. Mỗi vòng, gom các truy vấn theo midi, chạy lại quá trình từ đầu, dừng ở đúng các mốc midi để kiểm tra. Sau ⌈log2T⌉ vòng mọi khoảng co về một điểm.
  • Chia để trị trên đáp án (overall binary search): hàm solve(lo, hi, danh sách) nhận cả truy vấn lẫn cập nhật có liên quan tới khoảng đáp án [lo,hi], tách thành hai nửa rồi đệ quy. Cách này hợp với các bài "nhỏ thứ k".

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

Điều kiện cần: tính đơn điệu. Gọi Pi(t) là mệnh đề "truy vấn i được thỏa sau bước t" của một quá trình cố định (giống nhau cho mọi truy vấn). Nếu Pi(t) đúng thì Pi(t+1) cũng đúng (ví dụ thêm cạnh không bao giờ làm mất liên thông), nên đáp án ansi=min{t:Pi(t)} tìm được bằng chặt nhị phân. Đây là điều kiện duy nhất kỹ thuật cần.

Vì sao gộp được? Chặt nhị phân cho truy vấn i chỉ cần, ở mỗi bước, một câu trả lời Pi(midi). Quá trình thì giống nhau cho mọi truy vấn. Vậy nếu sắp các truy vấn theo midi rồi chạy quá trình một lượt t=1,2,…,T, thì tại mỗi t ta trả lời được mọi truy vấn có midi=t. Một lượt mô phỏng phục vụ tất cả Q truy vấn. Mỗi vòng khoảng [loi,hii] của mọi truy vấn giảm một nửa, nên chỉ cần ⌈log2(T+1)⌉ vòng.

Bổ đề cho dạng "nhỏ thứ k". Phần tử nhỏ thứ k của một tập bội S là ≤mid khi và chỉ khi |{x∈S:x≤mid}|≥k. Vế phải đơn điệu theo mid, nên đây cũng là chặt nhị phân, với "quá trình" là đếm các phần tử ≤mid. Trong chia để trị: ở đoạn đáp án [lo,hi], chỉ các cập nhật có giá trị trong [lo,mid] được đưa vào cây Fenwick. Truy vấn nào đếm được c≥k thì đáp án nằm ở nửa trái. Ngược lại nó sang nửa phải với k←k−c: c phần tử nhỏ hơn đã được "trả trước", nửa phải không cần thấy lại chúng. Mỗi cập nhật cũng chỉ đi về đúng một nửa (theo giá trị của nó), nên mỗi tầng đệ quy xử lý mỗi sự kiện đúng một lần.

Giữ thứ tự thời gian. Khi tách danh sách sự kiện thành hai nửa, giữ nguyên thứ tự xuất hiện. Nhờ vậy tại lúc gặp một truy vấn, cây Fenwick chứa đúng các cập nhật xảy ra trước nó, kể cả khi có thao tác xóa. Đây là lý do một cập nhật "gán ap=x" được tách thành hai sự kiện: xóa giá trị cũ, thêm giá trị mới.

Ví dụ chạy tay

Đồ thị 6 đỉnh, các cạnh được thêm lần lượt theo thời gian:

t = 1: 1 - 2        t = 3: 2 - 3
t = 2: 3 - 4        t = 4: 4 - 5          (đỉnh 6 không có cạnh nào)

sau t = 4:   1 - 2 - 3 - 4 - 5      6

Năm truy vấn: thời điểm sớm nhất mà hai đỉnh liên thông. Đáp án nằm trong [1,5], trong đó 5=m+1 nghĩa là "không bao giờ".

Truy vấn (u,v) Vòng 1: mid / kết quả Khoảng sau vòng 1 Vòng 2: mid / kết quả Khoảng sau vòng 2 Vòng 3 Đáp án
0 (1,4) 3 / liên thông [1,3] 2 / chưa [3,3] xong 3
1 (3,5) 3 / chưa [4,5] 4 / liên thông [4,4] xong 4
2 (1,2) 3 / liên thông [1,3] 2 / liên thông [1,2] mid=1 / liên thông, [1,1] 1
3 (2,5) 3 / chưa [4,5] 4 / liên thông [4,4] xong 4
4 (1,6) 3 / chưa [4,5] 4 / chưa [5,5] xong −1

Vòng 1 chỉ cần một lượt thêm cạnh t=1..4: tất cả truy vấn đều có mid=3, được kiểm tra ngay sau khi thêm cạnh t=3. Vòng 2 truy vấn 0 và 2 được kiểm tra sau cạnh t=2, ba truy vấn còn lại sau cạnh t=4, vẫn trong cùng một lượt. Vòng 3 chỉ còn truy vấn 2. Tổng cộng 3 lượt mô phỏng thay vì 5×3=15 nếu chặt nhị phân riêng từng truy vấn.

Cài đặt

Theo vòng: thời điểm sớm nhất hai đỉnh liên thông

Dữ liệu: n m q, m cạnh theo thứ tự thời gian, q truy vấn u v. In thời điểm sớm nhất (bằng 0 nếu u=v, −1 nếu không bao giờ).

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

struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) {
        while (p[x] != x) x = p[x] = p[p[x]];   // nén đường (halving)
        return x;
    }
    void unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a, sz[a] += sz[b];
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> eu(m + 1), ev(m + 1);
    for (int t = 1; t <= m; t++) cin >> eu[t] >> ev[t];
    vector<int> qu(q), qv(q), lo(q), hi(q);
    for (int i = 0; i < q; i++) {
        cin >> qu[i] >> qv[i];
        // đáp án nằm trong [1, m+1]; m+1 nghĩa là "không bao giờ liên thông"
        lo[i] = 1, hi[i] = m + 1;
        if (qu[i] == qv[i]) lo[i] = hi[i] = 0;   // trùng đỉnh: liên thông từ đầu
    }
    vector<vector<int>> bucket(m + 2);
    while (true) {
        bool changed = false;
        for (int t = 0; t <= m + 1; t++) bucket[t].clear();
        for (int i = 0; i < q; i++)
            if (lo[i] < hi[i]) bucket[(lo[i] + hi[i]) / 2].push_back(i), changed = true;
        if (!changed) break;                       // mọi khoảng đã co về một điểm
        DSU d(n);                                  // mỗi vòng chạy lại quá trình từ đầu
        for (int t = 1; t <= m; t++) {
            d.unite(eu[t], ev[t]);                 // trạng thái sau khi thêm cạnh t
            for (int i : bucket[t]) {              // các truy vấn đang hỏi "mid = t?"
                if (d.find(qu[i]) == d.find(qv[i])) hi[i] = t;
                else lo[i] = t + 1;
            }
        }
    }
    for (int i = 0; i < q; i++) cout << (lo[i] == m + 1 ? -1 : lo[i]) << '\n';
}
Python
import sys


def main():
    data = sys.stdin.buffer.read().split()
    n, m, q = int(data[0]), int(data[1]), int(data[2])
    pos = 3
    eu = [0] * (m + 1)
    ev = [0] * (m + 1)
    for t in range(1, m + 1):
        eu[t], ev[t] = int(data[pos]), int(data[pos + 1])
        pos += 2
    qu, qv = [0] * q, [0] * q
    lo, hi = [1] * q, [m + 1] * q  # đáp án trong [1, m+1]; m+1 = không bao giờ
    for i in range(q):
        qu[i], qv[i] = int(data[pos]), int(data[pos + 1])
        pos += 2
        if qu[i] == qv[i]:
            lo[i] = hi[i] = 0  # trùng đỉnh: liên thông từ đầu

    def find(p, x):
        while p[x] != x:
            p[x] = p[p[x]]
            x = p[x]
        return x

    while True:
        bucket = [[] for _ in range(m + 2)]
        changed = False
        for i in range(q):
            if lo[i] < hi[i]:
                bucket[(lo[i] + hi[i]) // 2].append(i)
                changed = True
        if not changed:
            break  # mọi khoảng đã co về một điểm
        p = list(range(n + 1))  # mỗi vòng chạy lại quá trình từ đầu
        sz = [1] * (n + 1)
        for t in range(1, m + 1):
            a, b = find(p, eu[t]), find(p, ev[t])
            if a != b:
                if sz[a] < sz[b]:
                    a, b = b, a
                p[b] = a
                sz[a] += sz[b]
            for i in bucket[t]:  # các truy vấn đang hỏi "mid = t?"
                if find(p, qu[i]) == find(p, qv[i]):
                    hi[i] = t
                else:
                    lo[i] = t + 1
    out = [str(-1 if x == m + 1 else x) for x in lo]
    sys.stdout.write("\n".join(out) + "\n")


main()
Chia để trị trên đáp án: nhỏ thứ k trên đoạn, có cập nhật điểm

Dữ liệu: n q, mảng a1..an, rồi q thao tác 1 p x (gán ap=x) hoặc 2 l r k (in phần tử nhỏ thứ k của al..ar).

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

// Sự kiện: cập nhật (thêm/xóa giá trị v tại vị trí pos) hoặc truy vấn (l, r, k)
struct Event {
    bool isQuery;
    int pos, v, sign;  // cập nhật: sign = +1 (thêm) hoặc -1 (xóa); v là giá trị đã nén
    int l, r, k, id;   // truy vấn
};

int n;
vector<long long> bit;
vector<Event> ev;
vector<int> ans;

void add(int i, int d) {
    for (; i <= n; i += i & -i) bit[i] += d;
}
long long sum(int i) {
    long long s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
}

// Mọi truy vấn trong ids có đáp án (chỉ số giá trị) thuộc [lo, hi]; ids giữ thứ tự thời gian
void solve(int lo, int hi, vector<int>& ids) {
    if (ids.empty()) return;
    if (lo == hi) {
        for (int i : ids)
            if (ev[i].isQuery) ans[ev[i].id] = lo;
        return;
    }
    int mid = (lo + hi) / 2;
    vector<int> L, R;
    for (int i : ids) {
        Event& e = ev[i];
        if (!e.isQuery) {
            if (e.v <= mid) add(e.pos, e.sign), L.push_back(i);  // chỉ đếm giá trị <= mid
            else R.push_back(i);
        } else {
            long long c = sum(e.r) - sum(e.l - 1);  // số giá trị <= mid trong [l, r] lúc này
            if (e.k <= c) L.push_back(i);
            else e.k -= c, R.push_back(i);         // bỏ c giá trị nhỏ, tìm tiếp ở nửa phải
        }
    }
    for (int i : L)  // hoàn tác Fenwick để nửa phải bắt đầu từ cây rỗng
        if (!ev[i].isQuery) add(ev[i].pos, -ev[i].sign);
    vector<int>().swap(ids);  // giải phóng bộ nhớ trước khi đệ quy
    solve(lo, mid, L);
    solve(mid + 1, hi, R);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    vector<long long> a(n + 1), vals;
    for (int i = 1; i <= n; i++) cin >> a[i], vals.push_back(a[i]);
    vector<array<long long, 4>> qs(q);
    for (auto& t : qs) {
        cin >> t[0];
        if (t[0] == 1) cin >> t[1] >> t[2], vals.push_back(t[2]);
        else cin >> t[1] >> t[2] >> t[3];
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    auto id = [&](long long x) { return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin()); };

    vector<int> cur(n + 1);
    for (int i = 1; i <= n; i++) {  // giá trị ban đầu = sự kiện "thêm"
        cur[i] = id(a[i]);
        ev.push_back({false, i, cur[i], +1, 0, 0, 0, 0});
    }
    int nq = 0;
    for (auto& t : qs) {
        if (t[0] == 1) {  // gán a[p] = x: xóa giá trị cũ rồi thêm giá trị mới
            int p = t[1], x = id(t[2]);
            ev.push_back({false, p, cur[p], -1, 0, 0, 0, 0});
            ev.push_back({false, p, x, +1, 0, 0, 0, 0});
            cur[p] = x;
        } else {
            ev.push_back({true, 0, 0, 0, int(t[1]), int(t[2]), int(t[3]), nq++});
        }
    }
    bit.assign(n + 1, 0);
    ans.assign(nq, 0);
    vector<int> ids(ev.size());
    iota(ids.begin(), ids.end(), 0);
    solve(0, int(vals.size()) - 1, ids);
    for (int i = 0; i < nq; i++) cout << vals[ans[i]] << '\n';
}
Python
import sys


def main():
    data = sys.stdin.buffer.read().split()
    pos = 0
    n, q = int(data[0]), int(data[1])
    pos = 2
    a = [0] + [int(x) for x in data[pos : pos + n]]
    pos += n
    qs = []
    vals = set(a[1:])
    for _ in range(q):
        if data[pos] == b"1":
            qs.append((1, int(data[pos + 1]), int(data[pos + 2])))
            vals.add(int(data[pos + 2]))
            pos += 3
        else:
            qs.append((2, int(data[pos + 1]), int(data[pos + 2]), int(data[pos + 3])))
            pos += 4
    vals = sorted(vals)
    idx = {v: i for i, v in enumerate(vals)}

    # Sự kiện cập nhật: (0, pos, v, sign); truy vấn: [1, l, r, k, id] (k thay đổi được)
    ev = []
    cur = [0] * (n + 1)
    for i in range(1, n + 1):  # giá trị ban đầu = sự kiện "thêm"
        cur[i] = idx[a[i]]
        ev.append((0, i, cur[i], 1))
    nq = 0
    for t in qs:
        if t[0] == 1:  # gán a[p] = x: xóa giá trị cũ rồi thêm giá trị mới
            p, x = t[1], idx[t[2]]
            ev.append((0, p, cur[p], -1))
            ev.append((0, p, x, 1))
            cur[p] = x
        else:
            ev.append([1, t[1], t[2], t[3], nq])
            nq += 1
    bit = [0] * (n + 1)
    ans = [0] * nq

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

    def pref(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    # Khử đệ quy bằng ngăn xếp: (lo, hi, danh sách chỉ số sự kiện theo thời gian)
    stack = [(0, len(vals) - 1, list(range(len(ev))))]
    while stack:
        lo, hi, ids = stack.pop()
        if not ids:
            continue
        if lo == hi:
            for i in ids:
                if ev[i][0] == 1:
                    ans[ev[i][4]] = lo
            continue
        mid = (lo + hi) // 2
        left, right = [], []
        for i in ids:
            e = ev[i]
            if e[0] == 0:
                if e[2] <= mid:  # chỉ đếm giá trị <= mid
                    add(e[1], e[3])
                    left.append(i)
                else:
                    right.append(i)
            else:
                c = pref(e[2]) - pref(e[1] - 1)  # số giá trị <= mid trong [l, r] lúc này
                if e[3] <= c:
                    left.append(i)
                else:
                    e[3] -= c  # bỏ c giá trị nhỏ, tìm tiếp ở nửa phải
                    right.append(i)
        for i in left:  # hoàn tác Fenwick để nửa phải bắt đầu từ cây rỗng
            if ev[i][0] == 0:
                add(ev[i][1], -ev[i][3])
        stack.append((mid + 1, hi, right))
        stack.append((lo, mid, left))
    sys.stdout.write("".join(str(vals[x]) + "\n" for x in ans))


main()

Bản Python khử đệ quy bằng ngăn xếp (Python giới hạn độ sâu đệ quy). Thứ tự xử lý hai nửa không quan trọng vì cây Fenwick luôn được hoàn tác về rỗng trước khi chuyển sang nhánh khác. Trên máy thử với n=q=105: bản C++ chạy khoảng 0,15 giây, bản Python khoảng 4 giây.

Độ phức tạp

Cách cài Thời gian Bộ nhớ
Theo vòng (DSU) O(logm·(mα(n)+n+q)) O(n+m+q)
Chia để trị, nhỏ thứ k có cập nhật O((n+q)logVlogn) O(n+q)

(V≤n+q là số giá trị khác nhau sau khi nén.)

Theo vòng: có ⌈log2(m+1)⌉ vòng. Mỗi vòng dựng lại DSU O(n), thêm m cạnh và kiểm tra mỗi truy vấn đúng một lần.

Chia để trị: cây đệ quy trên đoạn giá trị [0,V−1] có O(logV) tầng. Ở mỗi tầng, mỗi sự kiện (cập nhật hoặc truy vấn) thuộc đúng một nút, và được xử lý bằng một thao tác Fenwick O(logn), cộng một thao tác hoàn tác. Tổng O((n+q)logVlogn). Bộ nhớ O(n+q) vì các danh sách con ở cùng một tầng rời nhau và danh sách cha được giải phóng trước khi đệ quy.

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

  • Không chạy lại quá trình từ đầu mỗi vòng: cách theo vòng bắt buộc khởi tạo lại DSU (hoặc mảng, cây Fenwick) ở đầu mỗi vòng. Quên bước này, vòng 2 kiểm tra trên trạng thái "sau bước m" của vòng 1 và mọi truy vấn trông như đã thỏa.
  • Khoảng đáp án thiếu giá trị "không bao giờ": nếu đặt hi=m thì truy vấn không bao giờ thỏa vẫn bị ép về m. Mở rộng tới m+1 (hoặc kiểm tra riêng ở bước cuối) rồi in −1.
  • Quên trừ k khi sang nửa phải: ở dạng nhỏ thứ k, truy vấn đi sang nửa phải phải giảm k đi số phần tử c đã đếm ở nửa trái. Không trừ thì nửa phải tìm phần tử thứ k trong số các phần tử lớn hơn mid, sai ngay ví dụ nhỏ.
  • So sánh k<c thay vì k≤c: khi c=k phần tử nhỏ thứ k chính là phần tử ≤mid, nên phải đi sang trái.
  • Phá thứ tự thời gian khi tách: nếu đưa mọi cập nhật lên trước truy vấn (ví dụ sắp lại danh sách), truy vấn sẽ thấy cả các giá trị được gán sau nó. Luôn duyệt và tách danh sách theo đúng thứ tự xuất hiện, và tách "gán ap=x" thành "xóa cũ, thêm mới".
  • Không hoàn tác cây Fenwick: sau khi xử lý một nút, phải gỡ các cập nhật đã thêm, nếu không nhánh tiếp theo đếm thừa. Đừng memset cả cây ở mỗi nút: đó là O(n) mỗi nút, tổng O(nV).

Biến thể / Mở rộng

  • Đáp án là số thực hoặc rất lớn: thay mid nguyên bằng một số vòng cố định (khoảng 40 đến 60 vòng với số thực), mỗi vòng vẫn một lượt mô phỏng.
  • Nhỏ thứ k trên đường đi của cây: đổi "đếm trên đoạn" thành đếm trên đường đi qua tổng tiền tố theo Euler tour và LCA, mỗi đường đi thành 4 truy vấn tiền tố.
  • Không có cập nhật: nhỏ thứ k trên đoạn tĩnh còn giải được trực tuyến bằng cây phân đoạn bền vững. Chặt nhị phân song song là lựa chọn khi có cập nhật hoặc khi "quá trình" không biểu diễn được bằng cấu trúc bền vững (ví dụ DSU với thao tác nối cạnh).
  • Liên hệ: đây là một dạng xử lý truy vấn offline, họ hàng với chia để trị và CDQ. Cấu trúc đếm bên trong thường là cây Fenwick.

Bài tập luyện

  • Số nhỏ thứ k (dhbb26dx0811_c): (Very Hard) Số nhỏ thứ k trên đoạn, có cập nhật điểm; đổi mọi thao tác thành dãy sự kiện thêm/xóa rồi chia để trị trên đáp án với cây Fenwick, đúng bản chia để trị ở phần cài đặt.
  • Bộ máy hành chính (icpc23mbf): (Expert) Cây bị chèn và xóa đỉnh liên tục, cần trọng số nhỏ thứ k trên đường đi. Biểu diễn cây bằng dãy ngoặc cố định, mỗi đường đi thành 4 tiền tố có dấu, rồi chặt nhị phân tổng thể trên giá trị với cây Fenwick theo vị trí ngoặc.
  • Cung đường leo núi (tddn26_trekking): (Expert) Tập điểm tới được với sức bền x là một đoạn lá của cây Kruskal, cần giá trị lớn thứ k trên đoạn đó khi có cập nhật điểm; trả lời offline bằng chặt nhị phân tổng thể trên giá trị.
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