Posted on 2009-08-28 10:35
reiks 阅读(368)
评论(0) 编辑 收藏 引用 所属分类:
算法与数据结构
#include <stdio.h>
#include <memory.h>
#define N 1000
class treearray
{
public:
int c[N],n;
void clear()
{
memset(this,0,sizeof(*this));
}
int lowbit(int x)
{
return x&(x^(x-1));
}
void change(int i,int d)
{
for (;i<=n;i+=lowbit(i)) c[i]+=d;
}
int getsum(int i)
{
int t;
for (t=0;i>0;i-=lowbit(i)) t+=c[i];
return t;
}
}t;
main()//附一个测试程序
{
int i,x;
t.clear();
scanf("%d",&t.n);
for (i=1;i<=t.n;i++)
{
scanf("%d",&x);
t.change(i,x);
}
for (;scanf("%d",&x),x;) printf("%d\n",t.getsum(x));
return 0;
}