Wiki › Thuật toán › Chia để trị

Chia để trị

huunguyen Updated Tháng sáu 2, 2026

Chia để trị (divide and conquer) là kỹ thuật giải một bài toán bằng cách tách nó thành các bài toán con cùng dạng nhỏ hơn, giải từng bài con (thường bằng đệ quy), rồi kết hợp lời giải con thành lời giải cho bài gốc. Rất nhiều thuật toán nền tảng — sắp xếp trộn, tìm kiếm nhị phân, lũy thừa nhanh, đếm nghịch thế, nhân đa thức Karatsuba — đều là chia để trị, và nhờ nó mà độ phức tạp tụt từ $O (N^{2})$ xuống $O (N \log N)$ , hoặc từ $O (N)$ xuống $O (\log N)$ .

Một thuật toán chia để trị gồm ba bước:

Chia (divide): tách bài toán kích thước $N$ thành $a$ bài con kích thước $N / b$ .
Trị (conquer): giải mỗi bài con — thường gọi đệ quy; khi bài con đủ nhỏ (trường hợp cơ sở) thì giải trực tiếp.
Kết hợp (combine): ghép kết quả các bài con thành kết quả bài gốc.

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

Vì sao chia để trị nhanh hơn cách ngây thơ? Mấu chốt nằm ở chỗ chi phí được phân tán trên một cây đệ quy có chiều cao chỉ $O (\log N)$ .

Khi ta chia đôi liên tục, sau $k$ lần kích thước còn $N / 2^{k}$ ; kích thước chạm $1$ khi $k = \log_{2} N$ . Cây đệ quy do đó chỉ cao $\log N$ tầng thay vì $N$ tầng như đệ quy giảm-một-đơn-vị. Nếu mỗi tầng tốn tổng cộng $O (N)$ để chia và kết hợp, toàn bộ chỉ tốn $O (N \log N)$ .

Điều khiến kỹ thuật này đúng là tính chất "bài con độc lập và cùng dạng": lời giải của nửa trái không phụ thuộc vào nửa phải, nên ta giải riêng rồi mới gộp. Phần "kết hợp" chính là nơi chứa toàn bộ sự thông minh:

Với merge sort, kết hợp = trộn hai dãy đã sắp xếp trong $O (N)$ (con trỏ chạy thẳng, không quay lui).
Với đếm nghịch thế, ngay trong bước trộn ta tranh thủ đếm luôn các cặp nghịch thế bắc cầu giữa hai nửa.
Với lũy thừa nhanh, ta khai thác $a^{n} = (a^{n / 2})^{2}$ để chỉ cần một bài con thay vì nhân $n$ lần.

Master Theorem — công cụ tính độ phức tạp

Với công thức đệ quy dạng $T (N) = a T (N / b) + O (N^{d})$ (có $a$ bài con kích thước $N / b$ , chi phí chia+kết hợp là $O (N^{d})$ ):

Điều kiện	Độ phức tạp	Trực giác
$d > \log_{b} a$	$O (N^{d})$	tầng trên cùng (gốc) chiếm phần lớn chi phí
$d = \log_{b} a$	$O (N^{d} \log N)$	mọi tầng tốn như nhau, có $\log N$ tầng
$d < \log_{b} a$	$O (N^{\log_{b} a})$	số lá ở đáy cây chiếm phần lớn chi phí

Ví dụ merge sort: $a = 2$ , $b = 2$ , $d = 1$ , $\log_{b} a = 1 = d \Rightarrow O (N \log N)$ .

Ví dụ chạy tay: Merge Sort trên `[5, 2, 4, 1, 3]`

Pha chia — cắt đôi đệ quy đến khi mỗi đoạn còn 1 phần tử:

                [5, 2, 4, 1, 3]
                /             \
          [5, 2]              [4, 1, 3]
          /    \              /       \
        [5]    [2]         [4]      [1, 3]
                                    /    \
                                  [1]    [3]

Pha trị + kết hợp — đi từ dưới lên, trộn các đoạn đã sắp xếp:

[5] + [2]      -> [2, 5]
[1] + [3]      -> [1, 3]
[4] + [1, 3]   -> [1, 3, 4]
[2, 5] + [1, 3, 4] -> ?

Xem chi tiết bước trộn cuối [2, 5] với [1, 3, 4], hai con trỏ i, j chạy thẳng:

trái:  [2, 5]      phải: [1, 3, 4]      kết quả: []
        i=0               j=0
2 vs 1 -> lấy 1 (phải)    j->1           [1]
2 vs 3 -> lấy 2 (trái)    i->1           [1, 2]
5 vs 3 -> lấy 3 (phải)    j->2           [1, 2, 3]
5 vs 4 -> lấy 4 (phải)    j->3 (hết phải)[1, 2, 3, 4]
còn lại trái: 5  -> đổ nốt              [1, 2, 3, 4, 5]

Mảng đã sắp xếp: [1, 2, 3, 4, 5]. Mỗi phần tử ở mỗi tầng chỉ bị "chạm" đúng một lần khi trộn, nên mỗi tầng tốn $O (N)$ ; có $\log N$ tầng $\Rightarrow O (N \log N)$ .

Cài đặt

Merge Sort

void merge_sort(vector<int>& a, int l, int r) {
    if (l >= r) return;              // trường hợp cơ sở: đoạn 0 hoặc 1 phần tử
    int mid = l + (r - l) / 2;       // tránh tràn khi l+r lớn
    merge_sort(a, l, mid);           // trị nửa trái
    merge_sort(a, mid + 1, r);       // trị nửa phải

    // Kết hợp: trộn hai nửa đã sắp xếp trong O(độ dài)
    vector<int> tmp;
    tmp.reserve(r - l + 1);
    int i = l, j = mid + 1;
    while (i <= mid && j <= r)
        tmp.push_back(a[i] <= a[j] ? a[i++] : a[j++]);  // <= giữ tính ổn định
    while (i <= mid) tmp.push_back(a[i++]);
    while (j <= r)   tmp.push_back(a[j++]);
    for (int k = l; k <= r; k++) a[k] = tmp[k - l];
}

Tìm kiếm nhị phân (đệ quy)

// Trả về chỉ số của target trong mảng ĐÃ SẮP XẾP a[l..r], hoặc -1.
int binary_search(const vector<int>& a, int l, int r, int target) {
    if (l > r) return -1;                       // không còn đoạn để xét
    int mid = l + (r - l) / 2;
    if (a[mid] == target) return mid;
    if (a[mid] < target)
        return binary_search(a, mid + 1, r, target);   // chỉ giữ nửa phải
    return binary_search(a, l, mid - 1, target);        // chỉ giữ nửa trái
}

Đếm nghịch thế (gộp vào merge sort)

// Đếm số cặp (i, j), i < j, a[i] > a[j]. Trả về long long vì có thể tới N(N-1)/2.
long long merge_count(vector<int>& a, int l, int r) {
    if (l >= r) return 0;
    int mid = l + (r - l) / 2;
    long long cnt = merge_count(a, l, mid) + merge_count(a, mid + 1, r);

    vector<int> tmp;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp.push_back(a[i++]);
        else {
            cnt += mid - i + 1;   // a[i..mid] đều > a[j] => góp (mid-i+1) nghịch thế
            tmp.push_back(a[j++]);
        }
    }
    while (i <= mid) tmp.push_back(a[i++]);
    while (j <= r)   tmp.push_back(a[j++]);
    for (int k = l; k <= r; k++) a[k] = tmp[k - l];
    return cnt;
}

Lũy thừa nhanh (binary exponentiation)

// Tính a^n mod m trong O(log n) bằng a^n = (a^(n/2))^2 [* a nếu n lẻ].
long long power(long long a, long long n, long long mod) {
    a %= mod;                       // phòng a >= mod
    if (n == 0) return 1 % mod;     // 1 % mod để xử lý mod == 1
    long long half = power(a, n / 2, mod);
    long long res = half * half % mod;       // bình phương
    if (n & 1) res = res * a % mod;          // nhân thêm a nếu n lẻ
    return res;
}

def power(a, n, mod):
    a %= mod
    if n == 0:
        return 1 % mod
    half = power(a, n // 2, mod)
    res = half * half % mod
    if n & 1:
        res = res * a % mod
    return res

# Python có sẵn, cũng O(log n):
pow(a, n, mod)

Độ phức tạp

Thuật toán	Thời gian	Bộ nhớ	Lý giải
Merge sort	$O (N \log N)$	$O (N)$	$\log N$ tầng, mỗi tầng trộn $O (N)$ ; cần mảng phụ `tmp` kích thước $N$
Đếm nghịch thế	$O (N \log N)$	$O (N)$	y hệt merge sort, chỉ thêm phép cộng $O (1)$ mỗi bước
Tìm kiếm nhị phân	$O (\log N)$	$O (\log N)$ đệ quy / $O (1)$ vòng lặp	mỗi bước bỏ một nửa; phiên bản đệ quy tốn $O (\log N)$ stack
Lũy thừa nhanh	$O (\log n)$	$O (\log n)$ đệ quy / $O (1)$ vòng lặp	mỗi lần đệ quy số mũ giảm còn một nửa

Với chiều cao stack đệ quy: mọi thuật toán trên đều chỉ đệ quy sâu $O (\log)$ (merge sort sâu $O (\log N)$ vì luôn chia đôi cân bằng), nên không lo tràn stack ngay cả khi $N$ tới hàng triệu — khác hẳn đệ quy giảm-một-đơn-vị (sâu $O (N)$ ).

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

Tràn số khi tính mid. Viết mid = (l + r) / 2 có thể tràn int khi l + r vượt $2^{31}$ . Dùng mid = l + (r - l) / 2.
Quên long long cho kết quả đếm nghịch thế. Số nghịch thế tối đa là $N (N - 1) / 2$ ; với $N = 10^{5}$ đã là $\approx 5 \times 10^{9}$ , tràn int. Biến đếm và các biến trung gian phải là long long.
Overflow trong phép nhân của lũy thừa nhanh. half * half với half cỡ $10^{9}$ cho tích cỡ $10^{18}$ , vượt int rất xa. Phải để a, half, res kiểu long long và lấy % mod ngay sau mỗi phép nhân.
Quên 1 % mod ở trường hợp cơ sở. Nếu mod == 1, đáp án luôn phải là $0$ ; trả về 1 cứng sẽ sai. Trả về 1 % mod.
Bài con không độc lập mà vẫn áp dụng. Chia để trị chỉ đúng khi hai nửa giải được riêng rồi gộp. Nếu lời giải nửa phải phụ thuộc nửa trái (vd cần trạng thái tích lũy), phải xử lý phần "vắt qua giữa" (cross-boundary) tách riêng — đây là chỗ hay quên (vd quên đếm các nghịch thế bắc cầu giữa hai nửa).
Sai biên đệ quy gây vòng lặp vô hạn. Trong tìm kiếm nhị phân, viết binary_search(a, l, mid, ...) (thay vì mid - 1) khi a[mid] > target sẽ không thu hẹp được đoạn khi l == mid, lặp vô tận. Luôn loại bỏ mid khỏi đoạn con.
Tìm kiếm nhị phân trên mảng chưa sắp xếp. Thuật toán chỉ đúng khi mảng đã sắp xếp tăng dần; quên sắp xếp trước sẽ cho kết quả sai nhưng không báo lỗi.

Biến thể / Mở rộng

Lũy thừa ma trận: thay phép nhân số bằng nhân ma trận trong lũy thừa nhanh để tính số Fibonacci thứ $n$ hay các hồi quy tuyến tính trong $O (k^{3} \log n)$ .
Nhân nhanh Karatsuba $O (N^{1.585})$ và FFT/NTT $O (N \log N)$ để nhân hai đa thức / số lớn — đều dựa trên chia để trị.
Closest pair of points (cặp điểm gần nhất) $O (N \log N)$ : chia mặt phẳng, xử lý dải giữa.
Tối ưu DP bằng chia để trị (Divide and Conquer Optimization): khi điểm tối ưu $o p t [i]$ đơn điệu, có thể tính một tầng DP trong $O (N \log N)$ thay vì $O (N^{2})$ . Đây là kỹ thuật nâng cao xuất hiện trong các bài hạng chuyên gia ở mục dưới.

Bài tập luyện

Lũy thừa modulo (modexp) — (Nghiệp dư) cài đặt trực tiếp lũy thừa nhanh $a^{b} mod (10^{9} + 7)$ , bài nhập môn chuẩn của binary exponentiation.
Lũy thừa bậc hai (expexp) — (Trung cấp) tính $a^{b^{c}} mod p$ , phải lồng hai lớp lũy thừa nhanh và rút gọn số mũ theo định lý Fermat nhỏ.
Nhà kính của Sprout (greenhouse) — (Chuyên gia) DP đặt $K$ điểm tối ưu, dùng kỹ thuật tối ưu DP bằng chia để trị / convex hull trick.
Người Ăn Bánh (pieaters) — (Chuyên gia) bài DP nâng cao minh họa Divide and Conquer Optimization trên đoạn.