Truy vấn tổng đoạn - Mảng bất biến trong C++

Cho mảng số nguyên. Tìm tổng các phần tử từ chỉ số i đến j. Mảng bất biến (không thay đổi), có nhiều truy vấn. Cần tối ưu thời gian thực thi cho số lượng truy vấn lớn. Ví dụ: A = [5, 8, 3, 6, 1, 2, 5], truy vấn (0, 3) → 5+8+3+6 = 22.

Giải pháp: Mảng tiền tố (Prefix Sum)

1. Tạo mảng B, B[i] lưu tổng từ 0 đến i
2. Truy vấn (i, j): trả về B[j] - B[i-1] (nếu i>0) hoặc B[j] (nếu i=0)

Chương trình C++

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

class NumArray {
public:
    vector<int> pre;
    
    NumArray(vector<int>& nums) {
        pre.clear();
        int n = nums.size();
        pre.resize(n);
        for (int i = 0; i < n; i++) {
            if (i == 0) pre[0] = nums[0];
            else pre[i] = pre[i - 1] + nums[i];
        }
    }
    
    int sumRange(int i, int j) {
        if (i == 0) return pre[j];
        return pre[j] - pre[i - 1];
    }
};

int main() {
    vector<int> v = {5, 8, 3, 6, 1, 2, 5};
    NumArray na(v);
    cout << na.sumRange(0, 2) << endl;  // 16
    cout << na.sumRange(2, 5) << endl;  // 12
    cout << na.sumRange(0, 5) << endl;  // 25
}

Đầu vào/Kết quả

Khởi tạo: [5,8,3,6,1,2,5]
sumRange(0,2) = 16
sumRange(2,5) = 12
sumRange(0,5) = 25

Độ phức tạp

• Khởi tạo: O(n)
• Mỗi truy vấn: O(1)
• Không gian: O(n)