Hướng dẫn giải

Bài toán yêu cầu tính tổng các phần tử trong mỗi cửa sổ trượt kích thước \(K\). Mặc dù có thể giải bài này bằng mảng cộng dồn (Prefix Sum), chúng ta cũng có thể duy trì tổng trượt trực tiếp bằng cách cộng thêm phần tử mới đi vào cửa sổ và trừ đi phần tử cũ vừa đi ra khỏi cửa sổ. Cách tiếp cận này giúp tiết kiệm bộ nhớ và thực hiện trực tiếp trên luồng dữ liệu trượt.

Công thức chuyển trạng thái tổng từ cửa sổ \([i-K, i-1]\) sang cửa sổ \([i-K+1, i]\): \[\text{Sum}_{\text{new}} = \text{Sum}_{\text{old}} + a[i] - a[i - K]\]

Độ phức tạp thời gian: \(O(N)\) Độ phức tạp không gian: \(O(1)\) (nếu không tính không gian lưu trữ mảng ban đầu).

Lưu ý: Giá trị tổng có thể vượt quá giới hạn của số nguyên 32-bit (int), do đó cần sử dụng kiểu dữ liệu số nguyên 64-bit (long long trong C++).

Mã nguồn C++ mẫu

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    if (!(cin >> n >> k)) return 0;

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

    // Tính tổng của cửa sổ đầu tiên
    long long current_sum = 0;
    for (int i = 0; i < k; i++) {
        current_sum += a[i];
    }
    cout << current_sum;

    // Trượt cửa sổ và cập nhật tổng
    for (int i = k; i < n; i++) {
        current_sum += a[i] - a[i - k];
        cout << " " << current_sum;
    }
    cout << "\n";
    return 0;
}