AcWing 795. 前缀和
原题链接
简单
C++ 代码
#include <iostream> //用树状数组维护的前缀和
#include <cstdio>
using namespace std;
int n,m;
const int N=1e5+10;
int c[N],a[N];
int lowbit(int x)
{
return x&(-x);
}
int getsum(int x)
{
int res=0;
while(x>0)
{
res+=c[x];
x-=lowbit(x);
}
return res;
}
void update(int x,int val)
{
a[x]+=val;
while(x<=n)
{
c[x]+=val;
x+=lowbit(x);
}
}
int main(void)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
update(i,a[i]);
}
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",getsum(b)-getsum(a-1));
}
}
hao