题目描述

输入很长的序列n，再进行m次查找，要求找出位于输入的两个位置中间所有数的加和

样例

5 3
2 1 3 6 4
1 2
1 3
2 4

算法1

前缀和

因为这个题目中只有查找两个数中间加和的操作，会发现有大量的相同操作(即暴力连续相加)，在这种情况下可以将数组存为前面所有元素的和(前缀和)，这样可以减少大量相同操作；

时间复杂度 $O(n)$

建立前缀和数组的时间复杂度是O(n)，每一次查询的时间复杂度都是O(1);

参考文献

C++ 代码

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

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> sum;      //选用数组也可；我这里使用vector进行前缀和数组的存储
    sum.emplace_back(0);
    for(int i = 0; i < n; ++i){
        int x;
        scanf("%d", &x);
        sum.emplace_back(sum[i] + x);
    }
    while(m--){
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", sum[r]-sum[l-1]);
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

使用暴力相加会超时

时间复杂度

参考文献

C++ 代码

blablabla