Chuyên đề thuật toán nền tảng

🧠 Chia để trị: Divide, Solve, Combine

Bài học này giúp học sinh hiểu tư duy chia bài toán lớn thành bài toán nhỏ, giải từng phần rồi kết hợp lại. Đây là nền tảng của Binary Search, Merge Sort, Quick Sort, Segment Tree và nhiều thuật toán hiện đại.

DivideChia bài toán
SolveGiải bài toán con
CombineGộp kết quả
Ứng dụngSort, Search, Segment Tree
Mục tiêuÝ tưởngMô phỏngCode mẫuỨng dụngMergeLỗi hay nhầmBài tập

Mục tiêu bài học

Học xong cần làm được

  • Hiểu nguyên lý chia để trị.
  • Biết tách bài toán lớn thành các phần nhỏ, giải từng phần rồi kết hợp.
  • Viết được hàm chia để trị đơn giản: tính tổng, tìm max, đếm số chẵn.
  • Nhận ra các bài có thể dùng Binary Search, Merge Sort, Segment Tree.

Ví dụ đời sống

  • Chia lớp thành nhóm nhỏ để kiểm tra bài nhanh hơn.
  • Tìm tên trong danh bạ đã sắp xếp bằng cách chia đôi.
  • Gộp hai danh sách đã sắp xếp thành một danh sách lớn.

1. Ý tưởng chia để trị

“Chia để trị” gồm 3 bước quan trọng:

1. Divide

Chia

Chia bài toán ban đầu thành hai hoặc nhiều bài toán nhỏ hơn.

2. Solve

Giải

Giải các bài toán con, thường bằng đệ quy hoặc một thuật toán phù hợp.

3. Combine

Kết hợp

Gộp kết quả các bài toán con để tạo ra kết quả cuối cùng.

Dấu hiệu nhận biết: đề bài có thể chia đoạn [l, r] thành [l, m] và [m+1, r], hoặc chia dữ liệu làm hai nửa rồi xử lý độc lập.
Không phải cứ có đệ quy là chia để trị. Chia để trị cần có ý tưởng chia bài toán thành bài toán con và thường có bước kết hợp kết quả.

2. Mô phỏng: tính tổng mảng bằng chia để trị

Với mảng 5 2 7 1 4 3 6 8, ta chia đôi đến khi còn một phần tử, sau đó cộng kết quả từ dưới lên.

Mảng hiện tại:
Nhấn “Bước tiếp” để quan sát quá trình chia và gộp.

3. Code mẫu: tính tổng dãy số bằng chia để trị

Nội dung gốc của bài là tính tổng mảng bằng chia để trị. Bản dưới đây viết rõ hơn, có kiểu dữ liệu long long để tránh tràn số khi tổng lớn.

#include 
using namespace std;

long long sumRange(const vector& a, int l, int r) {
    if (l == r) return a[l];          // bài toán nhỏ nhất

    int m = (l + r) / 2;
    long long leftSum = sumRange(a, l, m);
    long long rightSum = sumRange(a, m + 1, r);

    return leftSum + rightSum;        // kết hợp kết quả
}

int main() {
    int n;
    cin >> n;

    vector a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    cout << sumRange(a, 0, n - 1);
    return 0;
}
def sum_range(a, l, r):
    if l == r:
        return a[l]          # bài toán nhỏ nhất

    m = (l + r) // 2
    left_sum = sum_range(a, l, m)
    right_sum = sum_range(a, m + 1, r)

    return left_sum + right_sum

n = int(input())
a = list(map(int, input().split()))

print(sum_range(a, 0, n - 1))
Với bài chỉ tính tổng mảng, cách duyệt một vòng O(n) thường đơn giản hơn. Ví dụ này dùng để học tư duy chia để trị. Khi bài có nhiều truy vấn hoặc cấu trúc phức tạp hơn, tư duy này dẫn tới Segment Tree.

4. Ứng dụng

Ứng dụngCách chiaCách kết hợpĐộ phức tạp thường gặpGhi chú
Binary SearchChia đôi khoảng tìm kiếm.Giữ lại nửa có khả năng chứa đáp án.O(log n)Cần dữ liệu có thứ tự hoặc tính đơn điệu.
Merge SortChia mảng thành hai nửa.Gộp hai nửa đã sắp xếp.O(n log n)Tốt để hiểu tư duy chia rồi gộp.
Quick SortChia theo pivot.Nhỏ/lớn hơn pivot nằm đúng phía.Trung bình O(n log n)Không nên tự viết ẩu nếu chưa chắc.
Segment TreeChia đoạn thành hai nửa.Lưu kết quả đoạn cha từ hai đoạn con.Build O(n), query O(log n)Mạnh cho truy vấn đoạn.

5. Mô phỏng gộp hai mảng đã sắp xếp

Đây là bước “Combine” quan trọng trong Merge Sort. Khi hai nửa đã sắp xếp, ta dùng hai con trỏ để gộp thành một mảng tăng dần.

Mảng trái:
Mảng phải:
Kết quả:
Nhấn “Bước tiếp” để xem cách gộp hai mảng.

6. Khi nào nên dùng chia để trị?

Nên dùng
  • Bài toán chia được thành hai nửa tương tự nhau.
  • Kết quả bài lớn tạo được từ kết quả bài nhỏ.
  • Cần tối ưu từ O(n²) xuống O(n log n).
Cân nhắc
  • Bài chỉ cần một vòng lặp đơn giản.
  • Đệ quy quá sâu có nguy cơ tràn stack.
  • Bước kết hợp quá phức tạp.
Không nên ép dùng
  • Chia xong nhưng không giảm độ khó.
  • Không có điều kiện dừng rõ ràng.
  • Dữ liệu nhỏ và cách đơn giản đã đủ tốt.

7. Lỗi học sinh hay nhầm

Quên điều kiện dừng.
Với đoạn [l, r], thường dừng khi l == r hoặc l > r tùy bài.
Tính sai mốc giữa.
Nên dùng m = l + (r - l) / 2 khi chỉ số lớn.
Chia sai đoạn.
Nếu dùng [l, m] thì nửa phải phải là [m + 1, r], tránh lặp vô hạn.
Chỉ chia mà không biết gộp.
Bước kết hợp quyết định lời giải đúng hay sai.

8. Bài tập luyện tập phân loại

📘 Mức 1 - Cơ bản

  1. Tính tổng mảng bằng chia để trị.
  2. Tìm phần tử lớn nhất bằng chia để trị.
  3. Đếm số phần tử chẵn bằng chia để trị.

📗 Mức 2 - Trung bình

  1. Tìm min trong đoạn [l, r].
  2. Đếm số phần tử dương.
  3. Kiểm tra mảng có toàn số chẵn hay không.

📙 Mức 3 - Nâng cao

  1. Cài đặt Merge Sort.
  2. Đếm số cặp nghịch thế bằng Merge Sort.
  3. Tìm tổng lớn nhất của dãy con liên tiếp bằng chia để trị.

🐉 Mức 4 - HSG định hướng

  1. Xây dựng Segment Tree truy vấn tổng đoạn.
  2. Tìm cặp điểm gần nhất trên mặt phẳng bằng chia để trị.
  3. Divide and conquer optimization khi học DP nâng cao.
💡 Xem lời giải mẫu: tìm max bằng chia để trị 
#include 
using namespace std;

int maxRange(const vector& a, int l, int r) {
    if (l == r) return a[l];

    int m = (l + r) / 2;
    int leftMax = maxRange(a, l, m);
    int rightMax = maxRange(a, m + 1, r);

    return max(leftMax, rightMax);
}

int main() {
    vector a = {1, 7, 3, 9, 2, 8};
    cout << maxRange(a, 0, (int)a.size() - 1);
    return 0;
}
def max_range(a, l, r):
    if l == r:
        return a[l]

    m = (l + r) // 2
    return max(max_range(a, l, m), max_range(a, m + 1, r))

a = [1, 7, 3, 9, 2, 8]
print(max_range(a, 0, len(a) - 1))

9. Quiz kiểm tra nhanh

Câu 1. Chia để trị thường gồm những bước nào?
Câu 2. Với bài tính tổng đoạn [l, r], điều kiện dừng thường là:
Câu 3. Thuật toán nào là ví dụ điển hình của chia để trị?

Tổng kết

Chia để trị là tư duy rất quan trọng: chia bài toán, giải bài toán con, rồi kết hợp kết quả. Ví dụ tính tổng bằng chia để trị giúp học cấu trúc cơ bản; các ứng dụng mạnh hơn gồm Binary Search, Merge Sort, Quick Sort và Segment Tree.

➡ Tiếp theo: Merge Sort và các bài toán đếm nghịch thế, truy vấn đoạn.

⬅️ Quay lại chương 5