Chương trình C++ truy vấn tổng khoảng (Range Sum Query) không cập nhật

Tính tổng phần tử từ chỉ số i đến j trong mảng (range sum query). Nếu truy vấn nhiều lần, duyệt mỗi lần O(n) quá chậm. Giải pháp: tiền tính tổng tiền tố (prefix sum / cumulative sum), trả lời mỗi truy vấn O(1).

Thuật toán

1. Xây dựng mảng prefix sum: c_arr[i] = arr[0] + ... + arr[i].
2. Truy vấn sum(i, j): - Nếu i == 0: trả về c_arr[j] - Ngược lại: c_arr[j] - c_arr[i-1]

Code ví dụ

#include <iostream>
#include <vector>
using namespace std;

void buildPrefixSum(const vector<int>& arr, vector<long long>& prefix) {
    int n = arr.size();
    prefix.resize(n);
    prefix[0] = arr[0];
    for(int i = 1; i < n; i++)
        prefix[i] = prefix[i-1] + arr[i];
}

long long rangeSum(const vector<long long>& prefix, int i, int j) {
    if (i == 0) return prefix[j];
    return prefix[j] - prefix[i-1];
}

int main() {
    vector<int> data = {5, 4, 32, 8, 74, 14, 23, 65};
    vector<long long> prefix;
    
    buildPrefixSum(data, prefix);
    
    cout << "Range sum (2,5): " << rangeSum(prefix, 2, 5) << endl; // 32+8+74+14=128
    cout << "Range sum (0,3): " << rangeSum(prefix, 0, 3) << endl; // 5+4+32+8=49
    cout << "Range sum (4,7): " << rangeSum(prefix, 4, 7) << endl; // 74+14+23+65=176
    
    return 0;
}

Kết quả

Range sum (2,5): 128
Range sum (0,3): 49
Range sum (4,7): 176

Độ phức tạp

• Tiền xử lý: O(n) thời gian, O(n) không gian.
• Mỗi truy vấn: O(1).
• Tổng cho Q truy vấn: O(n + Q) - tốt hơn nhiều so với O(n×Q).

Mở rộng: Fenwick Tree / Segment Tree

Nếu có cập nhật (update) giá trị mảng giữa các truy vấn, dùng Fenwick Tree (BIT) hoặc Segment Tree: cả update và query đều O(log n).