高级数据结构入门题目。

树状数组基本操作。

虽然线段树也可以做。

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,i,num[100001],t[200001],l,r; 
int lowbit(int x){
    return x&(-x);
}
void change(int x,int p){ 
    while(x<=n){
        t[x]+=p;
        x+=lowbit(x);
    }
    return;
}
int sum(int k){
    int ans=0;
    while(k>0){
        ans+=t[k];
        k-=lowbit(k);
    }
    return ans;
}
int ask(int l,int r){
    return sum(r)-sum(l-1); 
}
int main(int argc,char *argv[]){
    cin>>n>>m;
    for(i=1;i<=n;i++){
        cin>>num[i];
        change(i,num[i]);
    }
    for(i=1;i<=m;i++)
    {
        cin>>l>>r;
        cout<<ask(l,r)<<endl;
    }
    return 0;
}