Kỹ Thuật Chia Để Trị

1. Cầu nối tư duy: Recurrence $\to$ recursion tree $\to$ complexity

Ở Chuyên đề 10, chúng ta đã làm chủ kỹ thuật Đệ quy: giải bài toán quy mô $N$ bằng cách thu nhỏ dần bài toán. Từ cấu trúc code đệ quy, ta có thể thiết lập Hệ thức truy hồi (Recurrence) và phân tích qua Cây đệ quy (Recursion Tree) để tìm ra độ phức tạp chính xác:

$\text{Code Đệ Quy} \longrightarrow \text{Hệ Thức Truy Hồi (Recurrence)} \longrightarrow \text{Cây Đệ Quy (Recursion Tree)} \longrightarrow \text{Độ Phức Tạp (Complexity)}$

• Đệ quy tuyến tính (Chuyên đề 10): $$T(N) = T(N-1) + \mathcal{O}(1) \implies \text{Cây 1 nhánh thẳng, độ sâu } N \implies \Theta(N)$$

• Đệ quy phân nhánh chia đôi (Chuyên đề 11): $$T(N) = 2T\left(\frac{N}{2}\right) + \mathcal{O}(N) \implies \text{Cây nhị phân đầy đủ, chiều cao } \log_2 N \implies \Theta(N \log N)$$

• Đệ quy phân nhánh giảm 1 (Chuyên đề 10): $$T(N) = 2T(N-1) + \mathcal{O}(1) \implies \text{Cây nhị phân bùng nổ, } 2^N \text{ lá} \implies \Theta(2^N)$$

Quy luật cốt lõi: "Đệ quy" chỉ là cơ chế cài đặt; cấu trúc cây lời gọi và khối lượng công việc ở mỗi tầng mới là yếu tố quyết định độ phức tạp.

2. Phân biệt cốt lõi: Đệ quy (Recursion) và chia để trị (Divide & Conquer)

Học sinh rất dễ nhầm lẫn giữa hai khái niệm này:

• Tính $N! = N \times (N-1)!$ là Đệ quy nhưng không phải D&C (vì chỉ thu nhỏ 1 phần tử mà không có bước chia và gộp cấu trúc).
• Merge Sort là D&C hoàn chỉnh sử dụng cơ chế Đệ quy để điều khiển.

3. Bản chất vấn đề & hai kiểu phân rã: Divide vs partition

Divide & Conquer là chiến lược phân rã một bài toán thành các bài toán con có cùng bản chất nhưng kích thước nhỏ hơn, giải các bài toán con, rồi kết hợp kết quả lại để thu được lời giải cho bài toán ban đầu.

Phân biệt hai kiểu phân rã dữ liệu:

1. Divide (Phân chia theo vị trí chỉ số): * Chia cố định theo chỉ số mảng (thường là tại trung điểm mid = l + (r - l) / 2). * Ví dụ: Merge Sort chia [1 2 3 4 5 6 7 8] thành [1 2 3 4] và [5 6 7 8].
2. Partition (Phân hoạch theo quan hệ với Pivot): * Chia động dựa trên việc so sánh các phần tử với một giá trị chốt (pivot), kích thước 2 nửa có thể không đều nhau. * Ví dụ: QuickSelect phân hoạch [7 2 9 1 5 3 8] với pivot = 5 thành [2 1 3] (nhỏ hơn 5), [5], và [7 9 8] (lớn hơn 5).

4. Khung tư duy d&c (the d&c mental model)

Trước bất kỳ bài toán nào nghi ngờ sử dụng Chia Để Trị, hãy luôn trả lời 4 câu hỏi định hướng:

1. Tôi chia bài toán ở đâu? (Tại điểm giữa $mid$, theo trục tọa độ $x$, hay qua $pivot$?)
2. Bài toán con có kích thước bao nhiêu? ($N/2, N_1, N_2$?)
3. Tôi cần giải bao nhiêu bài toán con? (Chỉ 1 nhánh như Binary Search/QuickSelect hay cả 2 nhánh như Merge Sort?)
4. Tôi combine kết quả của các bài toán con như thế nào? (Đây là bước quyết định độ phức tạp!)

5. Mô phỏng từng bước thuật toán sắp xếp trộn (Merge Sort simulation)

Xét mảng ban đầu: A = [38, 27, 43, 3, 9, 82, 10].

Sơ đồ cây phân rã & gộp mảng (divide & merge tree):

6. Combine step & loop invariant — Trái tim của Divide & Conquer

Chân lý sư phạm: Sức mạnh và sự tinh tế của Chia Để Trị không nằm ở việc "bẻ nhỏ bài toán", mà nằm ở cách ta xử lý và kết hợp (Combine) các kết quả ở pha Unwinding.

Bất biến vòng lặp (loop invariant) trong hàm merge():

Khi gộp 2 mảng con đã sắp xếp $a[l..mid]$ và $a[mid+1..r]$ vào $temp$:

• Bất biến: Tại mỗi bước lặp, mảng đệm $temp[l..k-1]$ luôn chứa chính xác $(k - l)$ phần tử nhỏ nhất đã được chọn từ hai nửa $a[l..mid]$ và $a[mid+1..r]$ theo thứ tự không giảm.
• Quy tắc chọn:
• Nếu $a[i] \le a[j]$: Chọn $a[i]$ đưa vào temp[k], tăng $i$ và $k$ (điều kiện $\le$ bảo toàn tính Stable Sort).
• Nếu $a[i] > a[j]$: Chọn $a[j]$ đưa vào temp[k], tăng $j$ và $k$.

7. Bảng trực giác recurrence & định lý thợ (Master Theorem)

Trước khi dùng công thức tổng quát, hãy nắm vững 4 hệ thức truy hồi kinh điển:

Công thức tổng quát (Master Theorem):

Với $T(N) = a \cdot T(N/b) + \Theta(N^d)$ ($a \ge 1, b > 1$):

1. $a < b^d$ ($\log_b a < d$): Chi phí ngoài đệ quy thống trị $\implies T(N) = \Theta(N^d)$.
2. $a = b^d$ ($\log_b a = d$): Chi phí phân bố đều trên $\log_b N$ tầng $\implies T(N) = \Theta(N^d \log N)$.
3. $a > b^d$ ($\log_b a > d$): Số nút lá bùng nổ thống trị $\implies T(N) = \Theta(N^{\log_b a})$ (ví dụ Karatsuba $a=3, b=2, d=1 \implies \Theta(N^{\log_2 3}) \approx \Theta(N^{1.585})$).

8. Bảng nhận diện dấu hiệu thuật toán (d&c pattern recognition)

9. Chuỗi chuyển giao tri thức: Merge $\to$ Merge Sort $\to$ inversion counting

Điểm đặc sắc nhất của chuyên đề là chuỗi kế thừa thuật toán:

$\text{Merge Step (2 con trỏ)} \longrightarrow \text{Merge Sort } \Theta(N \log N) \longrightarrow \text{Đếm Nghịch Thế (Inversion Count)}$

Ứng dụng đỉnh cao: Đếm cặp nghịch thế (inversion counting) $\mathcal{O}(N \log N)$

• Khái niệm: Cặp nghịch thế là cặp chỉ số $(i, j)$ sao cho $i < j$ nhưng $A_i > A_j$.

• Bất biến gộp kỳ diệu: Khi chia mảng thành $\text{Left}[l..mid]$ và $\text{Right}[mid+1..r]$ đã sắp xếp:

• Khi duyệt con trỏ $i$ trên $Left$ và $j$ trên $Right$, nếu $L[i] > R[j]$, thì do $L$ đã sắp xếp tăng dần, toàn bộ các phần tử từ $L[i]$ đến $L[mid]$ đều lớn hơn $R[j]$!

• Ta cộng ngay một lượng bằng $(mid - i + 1)$ vào biến đếm nghịch thế trong $\mathcal{O}(1)$ thao tác cộng dồn.

• Bước $merge$ vẫn tốn $\mathcal{O}(N)$ thời gian, giúp tổng thời gian đếm toàn bộ mảng đạt $\Theta(N \log N)$ chuẩn thi đấu thay vì $\mathcal{O}(N^2)$ vét cạn.

10. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Bẫy cấp phát bộ nhớ đệm trong Merge Sort: * Việc tạo các vector mới bên trong mỗi lần gọi mergeSort() gây thêm nhiều lần cấp phát/giải phóng động và sao chép dữ liệu, làm tăng constant factor. * Cách phòng chống: Khai báo một mảng đệm toàn cục duy nhất vector<long long> temp(N); và truyền tham chiếu vào hàm đệ quy để tái sử dụng cho mọi bước gộp, giữ Auxiliary Memory ở mức $\Theta(N)$.

2. Tràn số nguyên 32-bit khi đếm số cặp nghịch thế: * Số lượng cặp nghịch thế tối đa của mảng $N = 10^5$ là $N(N-1)/2 \approx 5 \times 10^9$ (vượt giới hạn của int $2 \times 10^9$). * Cách phòng chống: Biến đếm nghịch thế bắt buộc dùng kiểu long long.

3. Bẫy tràn số khi tính Midpoint: * Viết mid = (l + r) / 2; có thể tràn int khi $l + r > 2 \cdot 10^9$. Luôn viết: mid = l + (r - l) / 2;.

4. Bẫy bỏ sót đoạn crossing trong Maximum Subarray: * Đoạn con lớn nhất có thể nằm trọn bên trái, trọn bên phải, hoặc vắt ngang qua tâm $mid$. Bắt buộc phải tính $maxCrossingSum$ từ $mid$ lan sang 2 phía.

11. Mẫu cài đặt chuẩn thi đấu (competitive templates)

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

using ll = long long;

// 1. Thuật toán Merge Sort chuẩn O(N log N) dùng buffer tái sử dụng
void merge(vector<ll> &a, vector<ll> &temp, int l, int mid, int r) {

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        // <= giữ tính stable: phần tử bên trái thắng khi bằng nhau
        if (a[i] <= a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];
    for (int idx = l; idx <= r; ++idx) a[idx] = temp[idx];
}

void mergeSort(vector<ll> &a, vector<ll> &temp, int l, int r) {

    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(a, temp, l, mid);
    mergeSort(a, temp, mid + 1, r);
    merge(a, temp, l, mid, r);
}

// 2. Thuật toán Đếm Số Cặp Nghịch Thế O(N log N)
ll countInversions(vector<ll> &a, vector<ll> &temp, int l, int r) {

    if (l >= r) return 0;
    int mid = l + (r - l) / 2;
    ll inv = 0;
    inv += countInversions(a, temp, l, mid);
    inv += countInversions(a, temp, mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
            inv += (mid - i + 1); // Đếm O(1) nhờ cấu trúc đã sắp xếp
        }
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];
    for (int idx = l; idx <= r; ++idx) a[idx] = temp[idx];
    return inv;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<ll> a = {38, 27, 43, 3, 9, 82, 10};

    int n = a.size();
    vector<ll> temp(n);

    cout << "So cap nghich the: " << countInversions(a, temp, 0, n - 1) << "\n";
    return 0;
}