Phân tách nhị phân

Lưu ý

Trước khi bắt đầu

Đây không phải là một khái niệm chính thức trong sách giáo khoa, mà là một định hướng tư duy giúp tiếp cận bài toán hiệu quả hơn.

Ý tưởng

Ý tưởng cốt lõi là tìm cách đơn giản hoá bài toán bằng cách phân tách không gian kết quả thành hai tập đối lập, thay vì xử lý trực tiếp với nhiều biến số phức tạp. Cách tiếp cận này giúp đưa bài toán về dạng quen thuộc và dễ giải hơn.

Khi đó, bài toán trở nên tương tự như đang xử lý trên tập nhị phân (0–1).

Hãy cùng tìm hiểu ý tưởng “phân tách nhị phân” (binary splitting) thông qua hai ví dụ sau.

Ví dụ 1

Count Subarrays With Median K

Đề bài

Bài toán

Cho một dãy gồm n phần tử và một số nguyên X. Hãy đếm số đoạn con liên tiếp mà số trung vị của đoạn đó bằng X.

Ghi nhớ rằng:

Với độ dài lẻ l, trung vị là phần tử lớn thứ (l / 2) + 1.
Với độ dài chẵn l, trung vị là phần tử lớn thứ (l / 2).

Ràng buộc: 1 ≤ n ≤ 10^5

Link đề →

Lời giải

Ý tưởng chính

Ta sẽ định nghĩa hàm F(x) là số đoạn con có trung vị ≥ x. Khi đó, kết quả bài toán chính là:

F(X) − F(X + 1)

Lý do:

F(X) đếm số đoạn có trung vị lớn hơn hoặc bằng X.
F(X + 1) đếm số đoạn có trung vị lớn hơn hoặc bằng X + 1. ⇒ Phần chênh lệch chính là số đoạn có trung vị bằng X.

Cách tính F(x)

Với mỗi đoạn con, ta chia các phần tử thành 2 loại:

Nhóm nhỏ hơn x: gán giá trị −1.
Nhóm lớn hơn hoặc bằng x: gán giá trị +1.

Khi đó, bài toán trở thành: đếm số đoạn con liên tiếp sao cho tổng các giá trị sau khi quy đổi > 0. Đây chính là bài toán đếm số đoạn có tổng prefix sum > 0, một bài toán kinh điển.

Chi tiết

Gọi prefix[i] là tổng từ đầu đến vị trí i sau khi chuyển đổi −1/+1. Với mỗi i, ta muốn đếm số lượng j < i sao cho prefix[j] < prefix[i].

Việc đếm này có thể thực hiện hiệu quả bằng Fenwick Tree (Binary Indexed Tree) hoặc Segment Tree, với hai thao tác:

add(x) — thêm một giá trị prefix.
get(x) — đếm số lượng giá trị nhỏ hơn x.

Mặc dù có nhiều hướng tiếp cận, nhưng việc chuyển bài toán sang bài toán prefix sum nhị phân (−1, +1) giúp ta sử dụng các kỹ thuật quen thuộc để giải quyết hiệu quả.

Cài đặt

Code

class Solution {
    inline int lsb(int x) { return x & -x; }

    void add(int x, vector<int>& t) {
        for (x++; x < t.size(); x += lsb(x)) t[x]++;
    }

    int get(int x, vector<int>& t) {
        int s = 0;
        for (x++; x > 0; x -= lsb(x)) s += t[x];
        return s;
    }

    long long count(vector<int>& nums, int k) {
        int n = nums.size(), b = n, c = 0;
        vector<int> t(2 * n + 2); // Size to handle [-n, n] range
        add(b, t); // Initialize at offset (zero-based)
        long long r = 0;
        for (int x : nums) {
            c += x < k ? -1 : 1;
            r += get(c - 1 + b, t);
            add(c + b, t);
        }
        return r;
    }

public:
    int countSubarrays(vector<int>& nums, int k) {
        return count(nums, k) - count(nums, k + 1);
    }
};

C++ · Fenwick Tree trên prefix sum −1/+1

Ví dụ 2

Serval and Rooted Tree

Đề bài

Bài toán

Cho một cây có n đỉnh với gốc là đỉnh số 1. Mỗi đỉnh không phải lá sẽ được gán một phép toán: max hoặc min (biểu diễn lần lượt bằng 1 và 0).

Giả sử cây có k lá, hãy gán các số nguyên từ 1 đến k (mỗi số đúng một lần) vào các lá, sao cho giá trị tại gốc đạt lớn nhất có thể, theo quy tắc: mỗi đỉnh không phải lá sẽ lấy giá trị là max hoặc min của các con tuỳ theo phép toán đã gán.

Ràng buộc: 2 ≤ n ≤ 3 × 10⁵; phép toán tại mỗi đỉnh: 0 = min, 1 = max.

Link đề →

Lời giải

Ý tưởng lời giải

Giả sử đáp án cần tìm là một số X. Ta thử kiểm tra liệu có thể đặt các số ≥ X là 1, các số còn lại là 0. Khi đó:

Với mỗi node có phép toán max, chỉ cần ít nhất một nhánh con sinh ra giá trị 1 là đủ.
Với node có phép toán min, thì tất cả các nhánh con đều phải sinh ra giá trị 1.

Từ đây, bài toán trở thành: đếm số lượng tối thiểu các lá phải gán giá trị 1 (tức là ≥ X) để toàn bộ cây có thể tính ra giá trị 1 tại gốc.

Nếu số lượng lá phải gán 1 ≤ k − X + 1 (tức còn đủ số lớn hơn hoặc bằng X để gán vào lá), thì X là đáp án hợp lệ.

Kết luận

Ta có thể áp dụng nhị phân đáp án trên X từ 1 đến k và kiểm tra với mỗi X bằng cách:

Biến cây thành cây nhị phân 0/1.
Đếm số lượng 1 tối thiểu cần có ở lá để đảm bảo giá trị tại gốc là 1.

Mục tiêu cuối cùng là tìm giá trị lớn nhất của X sao cho điều kiện trên thoả mãn.

Tổng kết

Vì sao cách này hiệu quả

Qua hai ví dụ trên, có thể thấy rằng trong một số trường hợp, ta có thể áp dụng một chiến lược tiếp cận bài toán bằng cách phân chia kết quả thành hai tập đối lập, từ đó đơn giản hoá không gian bài toán.

Việc chia thành hai tập này giúp ta quy đổi bài toán ban đầu thành một bài toán con có cấu trúc quen thuộc hơn — thường là các bài toán đã có lời giải phổ biến hoặc mang tính chất “well-known”, cho phép ta áp dụng những phương pháp giải quyết hàn lâm và hiệu quả hơn.