士兵杀敌(一)
时间限制:1000 ms | 内存限制:65535 KB
难度:3
- 描述
南将军手下有N个士兵,分别编号1到N,这些士兵的杀敌数都是已知的。
小工是南将军手下的军师,南将军现在想知道第m号到第n号士兵的总杀敌数,请你帮助小工来回答南将军吧。
注意,南将军可能会问很多次问题。
区间求和
#include<stdio.h>
#include<string.h>
int num[1000010];
int main()
{
int m,n,a;
scanf("%d%d",&n,&m);
num[0]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
num[i]=num[i-1]+a;
}
int s,e;
while(m--)
{
scanf("%d%d",&s,&e);
printf("%d\n",num[e]-num[s-1]);
}
return 0;
}
树状数组
#include<stdio.h>
#include<string.h>
int num[10001000];
int main()
{
int m,n,a;
scanf("%d%d",&n,&m);
memset(num,0,sizeof(num));
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
int j=i;
while(j<=n)
{
num[j]+=a;
j+=j&(-j);
}
}
for(int i=0;i<m;i++)
{
int s,e;
int s1,s2;
scanf("%d%d",&s,&e);
s1=s2=0;
s-=1;
while(s>=1)
{
s1+=num[s];
s-=s&(-s);
}
while(e>=1)
{
s2+=num[e];
e-=e&(-e);
}
printf("%d\n",s2-s1);
}
return 0;
}