Editorial for tuongdai: Tượng Đài Bác Hồ

Hiểu bài toán

Bài toán yêu cầu tính tổng các phần tử trong một đoạn con của mảng nhiều lần. Cụ thể, với một mảng gồm $n$ số nguyên không âm $w1, w2, \dots, wn$ và $k$ truy vấn, mỗi truy vấn yêu cầu tính tổng $wu + w{u+1} + \dots + wv$. Với $n, k$ lên tới $10^5$, cần một phương pháp hiệu quả để xử lý các truy vấn này nhanh chóng.

Các cách tiếp cận

Cách Brute Force (Duyệt trực tiếp)

#include <stdio.h>

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    long long a[100005];
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    while (k--) {
        int u, v;
        scanf("%d %d", &u, &v);
        long long sum = 0;
        for (int i = u; i <= v; i++) {
            sum += a[i];
        }
        printf("%lld ", sum);
    }
    return 0;
}

• Time Complexity: O(k * n)
• Space Complexity: O(n)

Với mỗi truy vấn, ta duyệt qua các phần tử từ chỉ số $u$ đến $v$ và cộng dồn. Vì có $k$ truy vấn và mỗi truy vấn có thể duyệt qua $n$ phần tử, độ phức tạp thời gian là $O(k \cdot n)$. Với $n, k \le 10^5$, số bước thực hiện có thể lên tới $10^{10}$, gây ra tình trạng 'Time Limit Exceeded'.

Cách Mảng cộng dồn (Prefix Sum)

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    // Sử dụng mảng động hoặc mảng static lớn để lưu prefix sum
    long long *pref = (long long*)malloc((n + 1) * sizeof(long long));
    pref[0] = 0;

    for (int i = 1; i <= n; ++i) {
        long long w;
        scanf("%lld", &w);
        pref[i] = pref[i-1] + w;
    }

    for (int q = 0; q < k; ++q) {
        int u, v;
        scanf("%d %d", &u, &v);
        // Công thức tính tổng đoạn [u, v]
        long long ans = pref[v] - pref[u-1];
        printf("%lld", ans);
        if (q + 1 < k) putchar(' ');
    }
    putchar('\n');
    free(pref);
    return 0;
}

• Time Complexity: O(n + k)
• Space Complexity: O(n)

Phương pháp này xây dựng một mảng pref (mảng cộng dồn) sao cho pref[i] là tổng các phần tử từ $w1$ đến $wi$. Việc xây dựng mất $O(n)$. Với mỗi truy vấn $(u, v)$, tổng cần tìm bằng $pref[v] - pref[u-1]$. Mỗi truy vấn chỉ mất $O(1)$. Tổng thời gian là $O(n + k)$, hoàn toàn chấp nhận được với giới hạn đề bài.

Cách Mảng cộng dồn (Tối ưu)

#include <stdio.h>

long long dp[100001];

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    // Đọc và tính prefix sum ngay trong vòng lặp đầu
    long long val;
    scanf("%lld", &val);
    dp[0] = val;
    for (int i = 1; i < n; i++) {
        scanf("%lld", &val);
        dp[i] = dp[i-1] + val;
    }

    while (k--) {
        int x, y;
        scanf("%d %d", &x, &y);
        // Chuyển về chỉ số 0-based (nếu đầu vào là 1-based)
        x--; y--; 
        long long tong;
        if (x == 0) tong = dp[y];
        else tong = dp[y] - dp[x-1];
        printf("%lld ", tong);
    }
    return 0;
}

• Time Complexity: O(n + k)
• Space Complexity: O(n)

Đây là biến thể của phương pháp mảng cộng dồn. Code sử dụng mảng toàn cục (static) thay vì cấp phát động, có thể an toàn hơn trên một số môi trường thi đấu. Logic tính toán tương tự: lưu tổng dồn năm, truy vấn lấy hiệu. Lưu ý xử lý cẩn thận chỉ số (0-based hoặc 1-based) để tránh lỗi.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Mảng cộng dồn (Prefix Sum Array) là kỹ thuật chuẩn để xử lý bài toán tổng đoạn con với nhiều truy vấn, giúp giảm độ phức tạp từ $O(k \cdot n)$ xuống $O(n + k)$.
• Cần phân biệt rõ chỉ số đầu vào (thường là 1-based) và chỉ số mảng trong code (có thể là 0-based hoặc 1-based) để tính toán chính xác.

Lỗi thường gặp

• Lỗi tràn số (Integer Overflow): Tổng các phần tử có thể lên tới $10^5 \times 10^5 = 10^{10}$, vượt quá giới hạn của kiểu int (khoảng $2 \times 10^9$). Cần sử dụng kiểu dữ liệu lớn hơn như long long.
• Lỗi chỉ số mảng: Truy cập sai địa chỉ bộ nhớ do nhầm lẫn giữa $u, v$ (1-based) và $i$ (0-based). Ví dụ: pref[v] - pref[u-1] (1-based) tương đương pref[y] - pref[x-1] (0-based với $x=u-1, y=v-1$).