---
# System prepended metadata

title: Introduction to cdq's "divide and conquer" technique

---

Kĩ thuật dnc của cdq hay còn gọi là dnc trên truy vấn hoặc dnc trên mảng.

Ý tưởng tổng quát : 
1. Giả sử ta đang xét đoạn $[l..r]$ 
2. Gọi $mid = (l+r)/2$
3. Ta sẽ tính những ảnh hưởng (contribution) của những cập nhật trong đoạn $[l,mid]$ tác động lên những truy vấn trong đoạn $[mid+1,r]$.
4. Do ta đang xét 2 nửa của đoạn $[l,r]$ nên thứ tự thời gian không còn quan trọng nữa nên ở bước tính toán ta có thể sắp xếp,...
5. tiếp tục gọi đệ quy xét 2 đoạn con $[l.mid]$ và $[mid+1,r]$.

Bài toán : https://marisaoj.com/problem/562

Như phần ý tưởng tổng quát ở trên, bài toán này ta có thể tiếp cận như sau : 
Khi ta đang xét đoạn các truy vấn từ $[l,r]$.
Gọi $mid = (l+r)/2$, ta sẽ tính toán những đáp án của các cập nhật thêm vào trong đoạn $[l,mid]$ làm tăng đáp án cho các truy vấn trong đoạn $[mid+1,r]$.
Vì ở đây các cập nhật luôn xảy ra trước các truy vấn ta tính nên thứ tự thời gian không còn quan trọng nên ta có thể sort các truy vấn và cập nhật theo đầu mút trái $(l)$ giảm dần. 
Sau đấy ta sẽ duyệt qua toàn bộ những truy vấn và cập nhật sau khi đã sort, khi gặp cập nhật mà có thứ tự xuất hiện trong đoạn $[l,mid]$ thì ta sẽ dùng cây BIT để lưu lại đầu r, còn khi gặp truy vấn mà có thứ tự thời gian xuất hiện thuộc đoạn $[mid+1,r]$ thì ta sẽ dùng cây BIT để đếm toàn bộ những cập nhật có đầu mút phải ($r_j$ >= $r_i$).
Như vậy ta đã giải quyết bài toán trong độ phức tạp là $O(n \times log^2(n))$

Nhận xét: về cơ bản thì kĩ thuật này gần tương đồng với kĩ thuật chia căn truy vấn khi ta chia các truy vấn thành $\sqrt{q}$ block, và trả lời từng block sau khi cập nhật các block trước đó. Còn đối với kĩ thuật dnc này thì ta sẽ chia các truy vấn từ $[1,i-1]$ thành $log(n)$ block nên sẽ có độ phức tạp tốt hơn.
