树状数组和前缀和数组
前缀和 O(n)
#include <iostream>
using namespace std;
const int N = 1e6+10;
int s[N],a[N];
int main()
{
int n,m,l,r;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];
while (m -- ){
cin>>l>>r;
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}
树状数组 O(logn)
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N = 1e5+10;
int tree[N];
void add(int x,int c){
for(int i=x;i<N;i+=lowbit(i)) tree[i]+=c;
}
inline int query(int x){
int res=0;
for(int i=x;i;i-=lowbit(i)) res+=tree[i];
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++){
int num;cin>>num;
add(i,num);
}
while(m--){
int l, r;
cin>>l>>r;
cout<<query(r)-query(l-1)<<'\n';
}
return 0;
}