Ý tưởng giải quyết

Gọi ~s_i~ là tổng các phần tử từ vị trí ~i~ đến cuối dãy:

~s_i = a_i + a_{i+1} + \cdots + a_n~.

Nếu tính riêng từng tổng bằng một vòng lặp, thời gian có thể lên đến ~O(n^2)~, không phù hợp khi ~n~ lớn.

Nhận xét:

• ~s_n = a_n~.
• ~s_i = a_i + s_{i+1}~ với ~i = n-1, n-2, \ldots, 1~.

Vì vậy, ta duyệt dãy từ phải sang trái, cộng dồn và lưu tổng hậu tố tại từng vị trí.

Các bước thực hiện

1. Nhập ~n~ và dãy ~a~.
2. Khởi tạo biến tổng ~t = 0~ (kiểu long long).
3. Duyệt ~i~ từ ~n~ về ~1~:
   • Cập nhật ~t = t + a_i~.
   • Gán ~s_i = t~.
4. Duyệt ~i~ từ ~1~ đến ~n~ và in ~s_i~.

Minh họa

Với dãy 1 5 7 2 1, ta tính từ phải sang trái:

Kết quả theo thứ tự từ vị trí ~1~ đến ~5~ là 16 15 10 3 1.

Chương trình C++ tham khảo

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

int n;
long long a[1000005], s[1000005], t;

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

    t = 0;
    for (int i = n; i >= 1; i--) {
        t += a[i];
        s[i] = t;
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << ' ';
        cout << s[i];
    }
    cout << endl;
    return 0;
}

Độ phức tạp

• Thời gian: ~O(n)~, vì chỉ duyệt dãy một số lần cố định.
• Bộ nhớ: ~O(n)~, để lưu dãy và các tổng hậu tố.

Lưu ý

• Tổng có thể đạt tới ~10^{15}~, vượt phạm vi của int; cần dùng long long.
• Phải tính tổng từ cuối dãy về đầu dãy, nhưng in kết quả từ đầu dãy đến cuối dãy.
• Khi ~n = 1~, kết quả chính là phần tử duy nhất.
• Dãy có thể chứa số âm hoặc số ~0~; cách làm vẫn đúng.