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

Cần tính tổng các phần tử từ chỉ mục i đến j. Các truy vấn (i, j) thực hiện nhiều lần.

Ví dụ

Input: arr[] = {5, 6, 3, 4, 1}, i = 1, j = 3 
Output: 13

Giải thích

6 + 3 + 4 = 13 
sum[] = {5, 6+5, 3+6+5, 4+3+6+5, 1+4+3+6+5} = {5, 11, 14, 18, 19} 
sum[j] - sum[i-1] = sum[3] - sum[0] = 18 - 5 = 13

Logic cơ bản: lặp từ i đến j cộng dồn. Nhưng để tối ưu nhiều truy vấn, dùng mảng prefix sum: mỗi phần tử cộng với phần tử trước. Truy vấn O(1) bằng sum[j] - sum[i-1].

Ví dụ mã C++

#include <iostream> 
using namespace std; 

int rangeSum(int i, int j, int sum[]) { 
    if (i == 0) return sum[j]; 
    return sum[j] - sum[i - 1]; 
} 

int main() { 
    int arr[] = {5, 6, 3, 4, 1}; 
    int n = 5; 
    int sum[5]; 
    sum[0] = arr[0]; 
    for (int i = 1; i < n; i++) 
        sum[i] = arr[i] + sum[i - 1]; 
    cout << rangeSum(1, 3, sum) << endl; 
    return 0; 
}

Kết quả

13