CDQ Divide and Conquer

Wiki › Thuật toán

huunguyen · Last updated 8, Tháng 4, 2026, 16:04

CDQ Divide and Conquer (陈丹琦分治) là kỹ thuật offline xử lý các bài toán có dependency theo thứ tự thời gian: thao tác $i$ ảnh hưởng đến thao tác $j$ khi $i < j$ . Phân rã chia để trị để xử lý ảnh hưởng của nửa trái lên nửa phải.

Ứng dụng: Đếm cặp nghịch thế, bài toán 3D (thời gian × không gian × giá trị), DP với dependency phức tạp.

Ý tưởng

Cho mảng thao tác $[1, n]$ :

Đệ quy giải nửa trái $[1, m i d]$ .
Tính ảnh hưởng của $[1, m i d]$ lên $[m i d + 1, n]$ .
Đệ quy giải nửa phải $[m i d + 1, n]$ .

Bước 2 thường dùng merge sort để xử lý thêm một chiều.

Ứng dụng 1: Đếm cặp nghịch thế (Inversion Count)

long long merge_count(vector<int>& a, int l, int r) {
    if (l >= r) return 0;
    int mid = (l + r) / 2;
    long long cnt = merge_count(a, l, mid) + merge_count(a, mid+1, r);

    // Đếm cặp (i,j) với i <= mid < j và a[i] > a[j]
    int i = l, j = mid+1;
    vector<int> tmp;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) { tmp.push_back(a[i++]); }
        else { 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;
}

Ứng dụng 2: Bài toán 3D (đếm điểm trong hình hộp)

Cho $Q$ thao tác: thêm điểm $(x, y, z)$ hoặc hỏi số điểm với $x^{'} \leq x, y^{'} \leq y, z^{'} \leq z$ .

CDQ xử lý chiều thời gian bằng phân rã, merge sort xử lý chiều $x$ , Fenwick Tree xử lý chiều $y$ (hoặc $z$ ):

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

int bit[MAXN];
void add(int i, int v) { for (; i < MAXN; 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<int> ans;
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 của [l,mid] (thêm điểm) lên [mid+1,r] (truy vấn)
    // Sắp xếp theo x, dùng BIT theo y
    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) {
        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);
    }
    for (int y : to_undo) add(y, -1);   // rollback
}

Ứng dụng 3: DP Optimization

Một số bài DP có $d p [i] = {max}_{j < i, cond (j, i)} (d p [j] + w (j, i))$ với điều kiện 2D. CDQ giải trong $O (N \log^{2} N)$ :

void cdq_dp(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    cdq_dp(l, mid);
    // Tính ảnh hưởng của [l,mid] lên [mid+1,r]
    // Sắp xếp theo một chiều, dùng CHT/monotone stack theo chiều kia
    cdq_dp(mid+1, r);
}

Độ phức tạp

Bài toán	Độ phức tạp
Inversion count	$O (N \log N)$
3D bài toán (BIT + CDQ)	$O (N \log^{2} N)$
DP 2D dependency	$O (N \log^{2} N)$

Khi nào dùng CDQ?

Bài toán có dependency theo thứ tự thời gian (offline).
Bài toán $k$ -chiều ( $k \geq 3$ ) — giảm 1 chiều bằng CDQ.
DP với transition phụ thuộc hai chiều.
Thay thế cho data structure phức tạp hơn (persistent, 2D segment tree).

Bình luận

Không có bình luận tại thời điểm này.