Truy vấn tổng khoảng không cập nhật bằng C++ (Prefix Sum)

Cho mảng nguyên kích thước n. Cần tính tổng các phần tử từ chỉ số L đến R cho nhiều truy vấn. Ví dụ:

Input : arr[] = {1, 2, 3, 4, 5}  L = 1, R = 3  L = 2, R = 4 Output : 9  12 Input : arr[] = {1, 2, 3, 4, 5}  L = 0, R = 4  L = 1, R = 2 Output : 15  5

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

Hai giải pháp: vét cạn (Brute Force) và mảng tiền tố (Prefix Sum — hiệu quả).

Cách vét cạn

Với mỗi truy vấn, duyệt từ L đến R cộng dồn.

Ví dụ

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

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(int);
    int L1 = 1, R1 = 3;
    int L2 = 2, R2 = 4;
    int sum = 0;
    for(int i = L1; i <= R1; i++) sum += arr[i];
    cout << sum << "\n";
    sum = 0;
    for(int i = L2; i <= R2; i++) sum += arr[i];
    cout << sum << "\n";
}

Kết quả

9 12

Độ phức tạp mỗi truy vấn O(N), tổng O(N×Q) — chậm với Q lớn.

Cách hiệu quả: Mảng tiền tố (Prefix Sum)

Xây dựng mảng prefix[i] = tổng từ arr[0] đến arr[i]. Tổng đoạn [L, R] = prefix[R] - prefix[L-1] (nếu L > 0), ngược lại là prefix[R]. Truy vấn O(1).

Ví dụ

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

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(int);
    int L1 = 1, R1 = 3;
    int L2 = 2, R2 = 4;
    int prefix[n];
    int sum = 0;
    for(int i = 0; i < n; i++) {
        sum += arr[i];
        prefix[i] = sum;
    }
    if (L1) cout << prefix[R1] - prefix[L1 - 1] << "\n";
    else cout << prefix[R1] << "\n";
    if (L2) cout << prefix[R2] - prefix[L2 - 1] << "\n";
    else cout << prefix[2] << "\n";
}

Kết quả

9 12

Giải thích

Mảng prefix cho phép trả lời mỗi truy vấn trong O(1). Tổng thời gian O(N + Q) — tối ưu cho dữ liệu lớn.

Kết luận

Bài viết trình bày giải pháp truy vấn tổng khoảng không cập nhật bằng Prefix Sum. Cách vét cạn O(N×Q) và cách tối ưu O(N+Q) kèm code C++. Áp dụng tương tự cho C, Java, Python.