Posted on 2009-08-28 10:35
reiks 閱讀(397)
評論(0) 編輯 收藏 引用 所屬分類:
算法與數(shù)據(jù)結(jié)構(gòu)
#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;
}