Kỹ Thuật Cửa Sổ Trượt

1. Khái niệm & bản chất của kỹ thuật cửa sổ trượt

Kỹ thuật Cửa sổ trượt (Sliding Window Technique) là phương pháp tối ưu hóa trên cấu trúc dữ liệu mảng hoặc chuỗi nhằm giải quyết các bài toán liên quan đến đoạn con liên tiếp (Contiguous Subarray / Substring).

Thay vì phải tính toán lại từ đầu hàm mục tiêu trên từng đoạn con $[i \dots j]$ với độ phức tạp $\mathcal{O}(K)$ hoặc $\mathcal{O}(N)$, kỹ thuật này duy trì một "khung cửa sổ" $[L \dots R]$ và cập nhật trạng thái mục tiêu trong $\mathcal{O}(1)$ thời gian bằng cách: $$\text{State}_{\text{mới}} = \text{State}_{\text{cũ}} + \text{Phần tử nạp vào } A_R - \text{Phần tử nhả ra } A_{L-1}$$

2. Cơ chế chuyển dịch & phân tích độ phức tạp $\mathcal{O}(N)$

2.1. Cơ chế hai con trỏ cùng chiều ($L \longrightarrow R$)

• Con trỏ phải $R$ (Right / Lead pointer): Mở rộng biên phải để nạp thêm phần tử $A_R$ vào cửa sổ nhằm thỏa mãn điều kiện bài toán.
• Con trỏ trái $L$ (Left / Trail pointer): Co hẹp biên trái để loại bỏ phần tử $A_L$ ra khỏi cửa sổ nhằm tối ưu hóa kích thước hoặc khôi phục tính hợp lệ của cửa sổ.

2.2. Phân tích chi phí khấu hao (amortized complexity analysis)

Mặc dù thuật toán thường được cài đặt dưới dạng một vòng lặp while lồng bên trong một vòng lặp for:

• Con trỏ $R$ duyệt từ $0$ đến $N - 1$ (thực hiện đúng $N$ bước tăng).
• Con trỏ $L$ duyệt từ $0$ đến $N$ (thực hiện tối đa $N$ bước tăng).
• Mỗi phần tử trong mảng chỉ đi vào cửa sổ đúng 1 lần và ra khỏi cửa sổ tối đa 1 lần.

Do đó, tổng số thao tác thêm/bớt phần tử trong toàn bộ chương trình không bao giờ vượt quá $2N$. Độ phức tạp thời gian đạt $\mathcal{O}(N)$ tuyến tính tuyệt đối.

3. Phân loại hai dạng cửa sổ trượt chuẩn mực

3.1. Dạng 1: Cửa sổ cố định độ dài $K$ (fixed-size window)

Áp dụng cho các bài toán yêu cầu khảo sát mọi đoạn con liên tiếp có độ dài đúng bằng $K$.

• Công thức trượt $\mathcal{O}(1)$:
• Khởi tạo: $\text{Current\_Sum} = \sum_{i=0}^{K-1} A_i$.

• Trượt từ vị trí $i = K$ đến $N - 1$: $$\text{Current\_Sum} \leftarrow \text{Current\_Sum} + A_i - A_{i-K}$$

• Cập nhật giá trị cực trị: $\text{Ans} = \max(\text{Ans}, \text{Current\_Sum})$.

Ví dụ minh họa 1: Tìm tổng đoạn con $K = 3$ lớn nhất trên dãy $A = [2, 1, 5, 1, 3, 2]$

Bảng mô phỏng quá trình trượt cửa sổ:

$$\implies \text{Kết quả: Tổng lớn nhất của đoạn dài 3 là } \mathbf{9} \text{ (đoạn } [5, 1, 3]\text{), trượt trong đúng } \mathcal{O}(1) \text{ mỗi bước!}$$

3.2. Dạng 2: Cửa sổ biến thiên (variable-size window)

Áp dụng cho các bài toán tìm đoạn con liên tiếp dài nhất/ngắn nhất hoặc đếm số lượng đoạn con thỏa mãn điều kiện $f([L \dots R])$.

Ví dụ minh họa 2: Tìm đoạn con ngắn nhất có tổng $\ge S = 7$ trên $A = [2, 3, 1, 2, 4, 3]$

$$\implies \text{Kết quả: Độ dài ngắn nhất là } \mathbf{2} \text{ (đoạn } [2, 4] \text{ hoặc } [4, 3]\text{)!}$$

4. Điều kiện áp dụng & giới hạn thất bại khi mảng có số âm

4.1. Điều kiện tiên quyết: Tính đơn điệu của hàm trạng thái

Cửa sổ trượt biến thiên bắt buộc yêu cầu hàm mục tiêu phải có tính đơn điệu:

• Khi mở rộng $R$ ($R \to R + 1$): Trạng thái phải tăng dần (hoặc không giảm).
• Khi co hẹp $L$ ($L \to L + 1$): Trạng thái phải giảm dần (hoặc không tăng).

Đối với bài toán tổng đoạn con, điều này tương đương với điều kiện: Tất cả các phần tử trong mảng phải là số không âm ($A_i \ge 0$).

4.2. Giới hạn: Vì sao Sliding Window thất bại khi có số âm?

Xét mảng $A = [2, -5, 10, -2, 8]$ với mục tiêu tìm đoạn con ngắn nhất có tổng $\ge 8$.

• Khi $R$ nạp thêm số âm $-5$, tổng cửa sổ bị giảm.
• Khi $L$ dịch qua số âm $-5$, tổng cửa sổ lại tăng lên.
• Tính chất đơn điệu bị phá vỡ $\implies$ Con trỏ $L$ không thể đưa ra quyết định di chuyển một chiều chắc chắn $\implies$ Bỏ sót nghiệm tối ưu.
• Giải pháp chuẩn: Chuyển sang sử dụng Mảng cộng dồn (Prefix Sum) kết hợp Hàng đợi hai đầu (Deque) / Cây chỉ số Fenwick / Segment Tree.

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

Mẫu: Đoạn con liên tiếp ngắn nhất có tổng $\ge S$ ($A_i \ge 0$)

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

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

    int n;
    long long s;
    if (!(cin >> n >> s)) return 0;

    vector<long long> a(n);

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

    }

    int l = 0;
    long long current_sum = 0;
    int min_len = n + 1; // Khởi tạo vô cực

    // Duyệt con trỏ R tuyến tính O(N)
    for (int r = 0; r < n; ++r) {
        current_sum += a[r]; // Nạp a[r] vào cửa sổ

        // Co hẹp con trỏ L khi cửa sổ đã thỏa mãn điều kiện
        while (current_sum >= s) {
            min_len = min(min_len, r - l + 1); // Cập nhật độ dài nhỏ nhất
            current_sum -= a[l];               // Nhả a[l] ra khỏi cửa sổ
            ++l;                               // Dịch chuyển biên trái
        }
    }

    if (min_len > n) {

        cout << 0 << "\n"; // Không tồn tại đoạn thỏa mãn
    } else {
        cout << min_len << "\n";
    }

    return 0;
}

6. Kỹ thuật cửa sổ trượt với bảng đếm ký tự / trạng thái

Khi xử lý bài toán chuỗi ký tự (như Đoạn con dài nhất chứa tối đa $K$ ký tự khác nhau):

• Sử dụng mảng đếm tần suất int count[256] hoặc int count[26] và biến distinct_count lưu số ký tự khác nhau hiện có trong cửa sổ.
• Khi nạp ký tự $S[R]$: nếu count[S[R]] == 0, tăng distinct_count. Tăng count[S[R]]++.
• Khi distinct_count > K: co con trỏ $L$, giảm count[S[L]]--; nếu count[S[L]] == 0, giảm distinct_count. Tăng ++L.

7. Các bẫy lỗi thường gặp (bug traps)

1. Bẫy tràn số nguyên khi tính tổng cửa sổ: Tổng đoạn con của mảng $N = 10^5$ phần tử với $A_i = 10^9$ có thể lên tới $10^{14}$. Khai báo biến current_sum kiểu long long.
2. Bẫy điều kiện khởi tạo kết quả cực trị: Khi tìm $\min$, khởi tạo ans = n + 1 (hoặc $\infty$); khi không tìm thấy nghiệm phải in ra 0 hoặc -1 theo đúng quy cách đề bài.
3. Bẫy chỉ số âm khi trượt cửa sổ cố định: Luôn đảm bảo chỉ thực hiện phép trừ a[i - k] khi chỉ số $i \ge K$.