前缀和

/*
    暴力的话每一次查询用时O(n), 一共m次，总共时间复杂度O(mn)
    n,m <= 100000 
    mn = 1e10,超时
    前缀和优化，每一次查询用时O(1), 一共m次，总共O(n)
*/
#include <iostream>
using namespace std;
const int N = 1e5 + 10; 
int s[N];
int main(){
    int n, m;  cin >> n >> m;
    for(int i = 1; i <= n; i ++ )    cin >> s[i];
    for(int i = 1; i <= n; i ++ )   s[i] += s[i - 1];
    while(m -- ){
        int l, r;   cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

树状数组

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
int a[N], tr[N];
int n, q;
int lowbit(int x){
    return x & -x;
}
void add(int x, int y){
    for(int i = x; i <= n; i += lowbit(i) )   tr[i] += y;
}
int query(int x){
    int res = 0;
    for(int i = x; i ; i -= lowbit(i))  res += tr[i];
    return res;
}
int main(){
    scanf("%d%d", &n, &q);

    for(int i = 1; i <= n; i ++ )   scanf("%d", &a[i]);
    for(int i = 1; i <= n; i ++ )   add(i, a[i]);   

    int x, y;
    for(int i = 0; i < q; i ++ ){
        scanf("%d%d", &x, &y);
        cout << query(y) - query(x-1) << endl;
    }
    return 0;
}