题目

https://www.acwing.com/problem/content/description/797/

算法思想

本题目是一道计算区间和的经典例题，以示例进行解读：

原始数列[n] = 前缀和[n] - 前缀和[n-1]

因此对应于区间 [l, r] 来说

sum[l, r] = 前缀和[r] - 前缀和[l-1]

题解

#include <iostream>

const int N = 100010;
int arr[N];

int main()
{
    int n, m;
    std::cin >> n >> m;
    
    for(int i = 1; i <= n; ++i) 
    {
        std::cin >> arr[i];
        arr[i] += arr[i-1];
    }
    
    int l, r;
    while(m--) {
        std::cin >> l >> r;
        
        std::cout << arr[r] - arr[l-1] << std::endl;
    }
    
    return 0;
}

复杂度

时间复杂度：O(1)，空间复杂度：O(1)