Wiki › Thuật toán › CDQ Divide and Conquer

CDQ Divide and Conquer

huunguyen Updated Tháng sáu 2, 2026

CDQ Divide and Conquer (陈丹琦分治) là một kỹ thuật offline (xử lý toàn bộ truy vấn cùng lúc, không trả lời ngay) dùng chia để trị để xử lý các bài toán mà một phần tử trước ảnh hưởng tới một phần tử sau theo thứ tự thời gian. Ý tưởng cốt lõi: thay vì để mỗi phần tử "tự tìm" tất cả phần tử ảnh hưởng tới nó, ta tách dãy thành nửa trái và nửa phải, rồi tính gộp ảnh hưởng của cả nửa trái lên cả nửa phải một lần.

Nhờ đó nhiều bài toán $k$ chiều được giảm bớt một chiều: ví dụ bài đếm điểm thống trị 3 chiều (3D dominance) vốn cần cấu trúc dữ liệu phức tạp, nhờ CDQ chỉ còn $O (N \log^{2} N)$ với một Fenwick Tree đơn giản, thay vì $O (N^{2})$ ngây thơ hay $O (N \log^{2} N)$ với cây phân đoạn 2D nặng nề.

Trang này trình bày hai nhánh thường gặp dưới cùng một tư duy chia để trị:

CDQ trên truy vấn / điểm (offline): đếm nghịch thế, đếm điểm thống trị 3 chiều — tính ảnh hưởng nửa trái lên nửa phải bằng merge sort + Fenwick.
Chia để trị tối ưu DP (divide-and-conquer DP optimization): tăng tốc các công thức DP dạng chia nhóm có tính chất đơn điệu điểm chia.

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

Giả sử ta có dãy thao tác (hoặc điểm) đánh số $1 . . n$ theo thứ tự thời gian. Một cặp $(i, j)$ "tương tác" khi $i < j$ (thao tác trước ảnh hưởng tới thao tác sau). Tập tất cả các cặp $i < j$ chia làm ba loại khi cắt tại $m i d = ⌊ (l + r) / 2 ⌋$ :

Cả $i, j$ đều ở nửa trái $[l, m i d]$ .
Cả $i, j$ đều ở nửa phải $[m i d + 1, r]$ .
$i$ ở nửa trái, $j$ ở nửa phải ( $i \leq m i d < j$ ).

Loại 1 và loại 2 được giải bằng đệ quy trên từng nửa. Điều then chốt: loại 3 là phần duy nhất cần xử lý "thủ công" ở mỗi mức đệ quy, và nó có cấu trúc đẹp — mọi phần tử trái đều đứng trước mọi phần tử phải về thời gian. Vì thế khi xét loại 3 ta không còn quan tâm chiều thời gian nữa (nó đã được nửa-trái/nửa-phải bảo đảm), chỉ cần lo các chiều còn lại.

Đó là lý do CDQ giảm được một chiều: chiều thời gian "biến mất" trong bước trộn. Nếu bài toán có 3 chiều $(t, x, y)$ , thì:

Chiều $t$ (thời gian) do cấu trúc đệ quy chia đôi lo.
Chiều $x$ do sắp xếp / merge sort lo (đảm bảo ta quét các phần tử theo thứ tự $x$ tăng).
Chiều $y$ do Fenwick Tree lo (đếm số phần tử có $y$ thoả điều kiện).

Tính đúng đắn đến từ việc ba loại cặp ở trên vét cạn và rời nhau: mỗi cặp $(i, j)$ với $i < j$ được tính đúng một lần — hoặc trong đệ quy con, hoặc trong bước trộn ở đúng mức mà $i, j$ lần đầu bị tách về hai nửa.

Với chia để trị tối ưu DP, trực giác khác một chút nhưng cùng tinh thần "tính gộp ảnh hưởng trái → phải". Xét DP dạng:

$d p_{k} [i] = {min}_{j < i} (d p_{k - 1} [j] + C (j, i))$

Nếu gọi $o p t [i]$ là điểm chia $j$ tối ưu cho $d p_{k} [i]$ , và bài toán thoả tính chất đơn điệu điểm chia ( $i_{1} < i_{2} \Rightarrow o p t [i_{1}] \leq o p t [i_{2}]$ , hệ quả của bất đẳng thức tứ giác / quadrangle inequality), thì ta tính các $d p_{k} [i]$ theo kiểu chia để trị: tính $d p_{k} [m i d]$ trước, tìm $o p t [m i d]$ , rồi đệ quy nửa trái với khoảng tìm $o p t$ bị chặn trên bởi $o p t [m i d]$ , nửa phải bị chặn dưới bởi $o p t [m i d]$ . Tổng công sức tìm điểm chia mỗi tầng là $O (N)$ , có $O (\log N)$ tầng, nên một lớp $k$ tốn $O (N \log N)$ .

Ví dụ chạy tay: đếm cặp nghịch thế

Đếm nghịch thế là phiên bản 2 chiều đơn giản nhất của tư duy CDQ: chiều "thời gian" là chỉ số $i$ , chiều giá trị là $a_{i}$ ; ta đếm cặp $i < j$ mà $a_{i} > a_{j}$ .

Xét mảng:

chỉ số:  0   1   2   3
giá trị: 2   4   1   3

Cắt tại $m i d = 1$ : trái $= [2, 4]$ (chỉ số 0,1), phải $= [1, 3]$ (chỉ số 2,3).

Đệ quy nửa trái $[2, 4]$ : đã tăng dần → 0 nghịch thế. Nửa phải $[1, 3]$ : đã tăng dần → 0 nghịch thế.

Bây giờ đếm cặp loại 3 (trái với phải) bằng cách trộn hai dãy đã sắp:

trái  (đã sắp): [2, 4]        con trỏ i
phải  (đã sắp): [1, 3]        con trỏ j

Bước 1:  i->2 , j->1
         2 > 1  =>  mọi phần tử còn lại bên trái (2 và 4) đều > 1
                    cnt += (số phần tử trái còn lại) = 2
         lấy 1 ra, j tiến.   cnt = 2
         tmp = [1]

Bước 2:  i->2 , j->3
         2 <= 3 =>  không có nghịch thế, lấy 2 ra, i tiến.
         tmp = [1, 2]

Bước 3:  i->4 , j->3
         4 > 3  =>  số phần tử trái còn lại = 1 (chỉ còn 4)
                    cnt += 1.   cnt = 3
         lấy 3 ra, j tiến.
         tmp = [1, 2, 3]

Bước 4:  phải hết, đổ nốt trái: tmp = [1, 2, 3, 4]

Tổng nghịch thế $= 0 + 0 + 3 = 3$ . Kiểm tra tay: các cặp $(i, j)$ với $a_{i} > a_{j}$ là $(2, 1), (4, 1), (4, 3)$ — đúng 3 cặp. Mấu chốt là dòng cnt += mid - i + 1: khi phần tử phải $a_{j}$ nhỏ hơn phần tử trái $a_{i}$ đang xét, thì tất cả phần tử trái từ $i$ tới $m i d$ (đều $\geq a_{i}$ vì dãy trái đã sắp) cũng lớn hơn $a_{j}$ , nên cộng một lần cả cụm.

Cài đặt

1. Đếm nghịch thế bằng merge sort (CDQ 2 chiều)

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

// Trả về số cặp nghịch thế trong a[l..r], đồng thời sắp xếp a[l..r] tăng dần.
long long merge_count(vector<int>& a, int l, int r) {
    if (l >= r) return 0;                 // 0 hoặc 1 phần tử: không có nghịch thế
    int mid = (l + r) / 2;
    // Loại 1 + loại 2: nghịch thế nằm gọn trong một nửa
    long long cnt = merge_count(a, l, mid) + merge_count(a, mid + 1, r);

    // Loại 3: i ở nửa trái, j ở nửa phải. Hai nửa giờ đã sắp tăng.
    int i = l, j = mid + 1;
    vector<int> tmp;
    tmp.reserve(r - l + 1);
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp.push_back(a[i++]);        // a[i] không tạo nghịch thế với a[j]
        } else {
            // a[i] > a[j]: mọi phần tử trái từ i..mid đều > a[j]
            cnt += mid - i + 1;
            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;                            // long long: nghịch thế có thể tới ~N^2/2
}

2. CDQ 3 chiều: đếm điểm thống trị (3D dominance, offline)

Cho $Q$ thao tác theo thứ tự thời gian: hoặc thêm một điểm $(x, y)$ , hoặc hỏi số điểm đã thêm trước đó có $x^{'} \leq x$ và $y^{'} \leq y$ . Chiều thời gian do đệ quy lo, chiều $x$ do sắp xếp lo, chiều $y$ do Fenwick lo.

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

const int MAXN = 200005;
struct Op { int x, y, type, idx; };   // type 0 = thêm điểm, 1 = truy vấn

int bit[MAXN], n_bit;
void add(int i, int v) { for (; i <= n_bit; i += i & -i) bit[i] += v; }
int  query(int i) { int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }

vector<long long> ans;   // ans[idx] = đáp án cho truy vấn thứ idx

// Các thao tác ops[l..r] ĐANG được giữ theo thứ tự thời gian (chỉ số = thời gian).
void cdq(vector<Op>& ops, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    cdq(ops, l, mid);
    cdq(ops, mid + 1, r);

    // Ảnh hưởng: điểm "thêm" ở [l, mid] lên truy vấn ở [mid+1, r].
    // Gom riêng, sắp theo x để quét đồng bộ (giả lập merge theo chiều x).
    vector<Op*> left_adds, right_queries;
    for (int i = l;     i <= mid; i++) if (ops[i].type == 0) left_adds.push_back(&ops[i]);
    for (int i = mid+1; i <= r;   i++) if (ops[i].type == 1) right_queries.push_back(&ops[i]);

    sort(left_adds.begin(),     left_adds.end(),     [](Op* a, Op* b){ return a->x < b->x; });
    sort(right_queries.begin(), right_queries.end(), [](Op* a, Op* b){ return a->x < b->x; });

    int j = 0;
    vector<int> to_undo;
    for (auto* q : right_queries) {
        // Đẩy vào Fenwick mọi điểm thêm có x <= x của truy vấn hiện tại
        while (j < (int)left_adds.size() && left_adds[j]->x <= q->x) {
            add(left_adds[j]->y, 1);
            to_undo.push_back(left_adds[j]->y);
            j++;
        }
        ans[q->idx] += query(q->y);        // đếm điểm có y' <= y
    }
    for (int y : to_undo) add(y, -1);      // HOÀN TÁC Fenwick, KHÔNG memset toàn cục
}

3. Chia để trị tối ưu DP (divide-and-conquer DP optimization)

Mẫu cho $d p_{k} [i] = {min}_{j < i} (d p_{k - 1} [j] + C (j, i))$ thoả đơn điệu điểm chia. Với mỗi lớp $k$ ta gọi hàm solve một lần.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

int N, K;
vector<ll> dp_prev, dp_cur;        // dp_{k-1} và dp_k
ll C(int j, int i);                // chi phí đoạn (j, i], tự cài theo bài

// Tính dp_cur[l..r], biết điểm chia tối ưu nằm trong [optl, optr].
void solve(int l, int r, int optl, int optr) {
    if (l > r) return;
    int mid = (l + r) / 2;
    pair<ll,int> best = {INF, -1};
    int up = min(mid - 1, optr);
    for (int j = optl; j <= up; j++) {     // chỉ quét khoảng điểm chia hợp lệ
        ll val = dp_prev[j] + C(j, mid);
        if (val < best.first) best = {val, j};
    }
    dp_cur[mid] = best.first;
    int opt = best.second;
    // Đơn điệu: opt[l..mid-1] <= opt <= opt[mid+1..r]
    solve(l, mid - 1, optl, opt);
    solve(mid + 1, r, opt, optr);
}

Độ phức tạp

Bài toán	Thời gian	Bộ nhớ
Đếm nghịch thế (merge sort)	$O (N \log N)$	$O (N)$
CDQ 3 chiều (đếm điểm thống trị)	$O (N \log^{2} N)$	$O (N)$
Chia để trị tối ưu DP, $K$ lớp	$O (K \cdot N \log N)$	$O (N)$ (hoặc $O (K N)$ nếu lưu hết)

Lý giải:

Đếm nghịch thế: cây đệ quy có $O (\log N)$ tầng, mỗi tầng trộn tổng cộng $O (N)$ phần tử → $O (N \log N)$ . Bộ nhớ $O (N)$ cho mảng tạm và ngăn xếp đệ quy $O (\log N)$ .
CDQ 3 chiều: cũng $O (\log N)$ tầng đệ quy theo thời gian; mỗi tầng ta sắp xếp lại theo $x$ ( $O (N \log N)$ mỗi tầng) rồi quét với Fenwick ( $O (N \log N)$ ). Tổng $O (N \log^{2} N)$ . Mẹo giảm còn $O (N \log N)$ : thay sort mỗi tầng bằng merge sẵn theo $x$ trong quá trình đệ quy (như merge sort), khi đó chỉ còn một thừa số $\log$ từ Fenwick. Bộ nhớ $O (N)$ cho mảng Fenwick và các vector tạm.
Chia để trị tối ưu DP: ở mỗi tầng đệ quy của solve, tổng độ dài các khoảng $[o p t l, o p t r]$ được quét là $O (N)$ (các khoảng phủ chồng nhưng tổng biên $O (N)$ mỗi tầng), có $O (\log N)$ tầng → $O (N \log N)$ cho một lớp $k$ , nhân $K$ lớp. Bộ nhớ chỉ cần hai mảng $d p$ kề nhau, $O (N)$ ; nếu cần truy vết để in cấu hình thì lưu $O (K N)$ .

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

Tràn số khi đếm nghịch thế: số nghịch thế tối đa là $(\binom{N}{2}) \approx N^{2} / 2$ . Với $N = 2 \cdot 10^{5}$ con số này $\approx 2 \cdot 10^{10}$ , vượt int. Phải dùng long long cho biến đếm, nếu không sẽ Wrong Answer ở test lớn mà chạy đúng test nhỏ.
Không hoàn tác (rollback) Fenwick trong CDQ 3 chiều: nếu sau khi xử lý một mức đệ quy bạn memset(bit, 0, ...) toàn cục thì độ phức tạp phình lên $O (N^{2})$ và TLE. Phải chỉ trừ lại đúng những vị trí đã +1 (mảng to_undo). Ngược lại, nếu quên rollback hoàn toàn, các điểm của mức này sẽ "rò rỉ" sang mức khác và cho kết quả sai.
Sai thứ tự / biên khi xử lý cặp bằng nhau ( $\leq$ vs $<$ ): với 3D dominance, điều kiện thường là $x^{'} \leq x$ chứ không phải $x^{'} < x$ . Dùng nhầm < thay <= (hoặc ngược lại) làm sót/đếm dư các cặp có toạ độ trùng. Khi có nhiều điểm cùng $x$ , hãy quyết định rõ ràng quy tắc phá hoà (thường: cùng $x$ thì điểm "thêm" được xử lý trước truy vấn).
Trộn sai khiến chiều thời gian không còn được bảo đảm: nếu trong bước trộn theo $x$ bạn vô tình đảo thứ tự thời gian của các phần tử trong cùng một nửa, thì lần đệ quy sau sẽ tính sai cặp loại 3. Quy tắc: chỉ được sắp lại theo $x$ bên trong một lần gọi, còn ranh giới trái/phải theo thời gian phải do chỉ số $l, m i d, r$ quyết định trước khi sort.
Áp dụng chia để trị tối ưu DP khi không có đơn điệu điểm chia: kỹ thuật solve(l, r, optl, optr) chỉ đúng khi hàm chi phí $C$ thoả bất đẳng thức tứ giác (quadrangle inequality), kéo theo $o p t [i]$ không giảm. Nếu áp dụng bừa cho hàm chi phí bất kỳ, đáp án sẽ sai dù code "chạy ra số". Hãy kiểm chứng tính đơn điệu (bằng tay hoặc brute-force nhỏ) trước khi tin.
Off-by-one ở khoảng điểm chia: trong solve, giới hạn trên của $j$ phải là min(mid - 1, optr) (vì $j < i = m i d$ ). Quên mid - 1 sẽ cho phép $j \geq i$ , tạo ra chuyển trạng thái không hợp lệ; quên optr thì mất luôn tính chất tăng tốc, trở lại $O (N^{2})$ mỗi lớp.
Đệ quy solve sai khoảng truyền điểm chia: phải truyền solve(l, mid-1, optl, opt) và solve(mid+1, r, opt, optr). Đảo opt giữa hai nhánh sẽ chặt mất nghiệm đúng và cho kết quả nhỏ/lớn hơn thực tế.

Biến thể / Mở rộng

CDQ lồng CDQ: với bài 4 chiều, có thể dùng CDQ cho chiều thời gian, rồi bên trong lại CDQ cho một chiều nữa, để lại Fenwick lo chiều cuối — cho $O (N \log^{3} N)$ .
CDQ thay cho cấu trúc dữ liệu kiên cố (persistent): nhiều bài "truy vấn lịch sử" giải được offline bằng CDQ với bộ nhớ $O (N)$ thay vì cây phân đoạn persistent tốn $O (N \log N)$ bộ nhớ.
Liên hệ Knuth–Yao: khi DP có thêm tính đơn điệu hai phía mạnh hơn, có thể dùng tối ưu Knuth ( $O (N^{2})$ cho DP khoảng) thay cho chia để trị; cả hai cùng dựa trên bất đẳng thức tứ giác. Xem thêm trang Quy hoạch động tối ưu.

Bài tập luyện

Nghịch Thế Cửa Sổ Trượt (swinv) — (Nâng cao) Đếm nghịch thế trên cửa sổ trượt, làm quen tư duy "đếm cặp $i < j$ với $a_{i} > a_{j}$ " — nền tảng 2 chiều của CDQ trước khi lên 3 chiều.
Nhà kính của Sprout (greenhouse) — (Chuyên gia) DP chia $N$ cây thành $K$ nhóm với chi phí khoảng thoả bất đẳng thức tứ giác — bài mẫu để luyện chia để trị tối ưu DP $O (K N \log N)$ .
Người Ăn Bánh (pieaters) — (Chuyên gia) Tối ưu trên các đoạn $[l_{i}, r_{i}]$ kết hợp DP; rèn cách dựng công thức rồi tăng tốc bằng chia để trị.
Chuồng Bò Tròn Mới (cbarnrev) — (Chuyên gia) Chia vòng tròn thành $K$ đoạn liên tiếp cực tiểu tổng chi phí — chia để trị tối ưu DP trên cấu trúc vòng, mức khó cao nhất của thang.