HDU-1166-敌兵布阵(树状数组)
http://acm.hdu.edu.cn/showproblem.php?pid=1166
这题之前用线段树做的,现在用树状数组
先简单说下树状数组吧
如上图所示
c1 = a1
c2 = a1 + a2
c3 = a3
c4 = a1 + a2 + a3 + a4
c5 = a5
c6 = a5 + a6
c7 = a7
c8 = a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8
对于序列a,我们设一个数组C定义C[i] = a[i – 2^k + 1] + … + a[i],k为i在二进制下末尾0的个数
求2^k
int lowbit(int x)
{
return x&(x^(x-1));
}
将a[p]的值加上一个值x
void update(int p,int x)
{
while(p<=n)
{
c[p]+=x;
p+=lowbit(p);
}
}
求前p项和
int sum(int p)
{
int sum=0;
while(p>0)
{
sum+=c[p];
p-=lowbit(p);
}
return sum;
}
完整代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 50005
int a[N],c[N];
int n;
int lowbit(int x)
{
return x&(x^(x-1));
}
void update(int p,int x)
{
while(p<=n)
{
c[p]+=x;
p+=lowbit(p);
}
}
int sum(int p) //前p相的和
{
int sum=0;
while(p>0)
{
sum+=c[p];
p-=lowbit(p);
}
return sum;
}
int main()
{
int t,i,m,k;
int a1,a2;
char str[10];
scanf("%d",&t);
for(k=1;k<=t;k++)
{
scanf("%d",&n);
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
for(i=1;i<=n;i++) //初值为0
{
scanf("%d",&m);
a[i]+=m;
update(i,m);
}
printf("Case %d:\n",k);
while(scanf("%s",str),strcmp(str,"End"))
{
if(strcmp(str,"Add")==0)
{
scanf("%d%d",&a1,&a2);
a[a1]+=a2;
update(a1,a2);
}
else if(strcmp(str,"Sub")==0)
{
scanf("%d%d",&a1,&a2);
a[a1]-=a2;
update(a1,-a2);
}
else if(strcmp(str,"Query")==0)
{
scanf("%d%d",&a1,&a2);
printf("%d\n",sum(a2)-sum(a1-1));
}
}
}
return 0;
}
分享到:
相关推荐
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
算法-数塔(HDU-2084).rar
算术(HDU-6715).rar
算法-确定比赛名次(HDU-1285).rar
最短路(HDU-2544).rar
算法-命运(HDU-2571)(包含源程序).rar
算法-连连看(HDU-1175)(包含源程序).rar
算法-欧拉回路(HDU-1878)(包含源程序).rar
算法-六度分离(HDU-1869)(包含源程序).rar
算法-排列2(HDU-1716)(包含源程序).rar
算法-排列组合(HDU-1521)(包含源程序).rar
算法-迷宫城堡(HDU-1269)(包含源程序).rar