http://acm.hdu.edu.cn/showproblem.php?pid=1166
#include<stdio.h>
#define MAX 50001
#define lowbit(x) (x&(-x))
int sum[MAX],tree[MAX];
int query(int x)
{
int sum = 0;
while(x>0)
{
sum += tree[x];
x -= lowbit(x);
}
return sum;
}
void add(int a,int b,int n)
{
while(a<=n)
{
tree[a] += b;
a += lowbit(a);
}
}
int main()
{
int T,n,i,cas,data;
scanf("%d",&T);
for(cas=1;cas<=T;cas++)
{
scanf("%d",&n);
tree[0] = sum[0] = 0;
for(i=1;i<=n;i++)
{
scanf("%d",&data);
sum[i] = sum[i-1] + data;
tree[i] = sum[i] - sum[i - lowbit(i)];
}
char com[10];
int a,b;
printf("Case %d:\n",cas);
while(scanf("%s",com),com[0]-'E')
{
scanf("%d%d",&a,&b);
if(com[0]=='Q')
printf("%d\n",query(b) - query(a-1));
else if(com[0]=='A')
add(a,b,n);
else
add(a,-b,n);
}
}
return 0;
}
二維的話就這樣抄作
int query(int x,int y)
{
int sum=0;
while(x>0)
{
int tmp = y;
while(tmp>0)
{
sum += tree[x][tmp];
tmp -= lowbit(tmp);
}
x -= lowbit(x);
}
return sum;
}
void add(int x,int y,int num)
{
while(x<=MAX)
{
int tmp = y;
while(tmp<=MAX)
{
tree[x][tmp] += num;
tmp += lowbit(tmp);
}
x += lowbit(x);
}
}
兩道赤裸裸的二維樹形數組
http://acm.hdu.edu.cn/showproblem.php?pid=1892http://acm.hdu.edu.cn/showproblem.php?pid=2642 稍微變化一點
http://acm.hdu.edu.cn/showproblem.php?pid=1541 http://acm.hdu.edu.cn/showproblem.php?pid=2227http://acm.hdu.edu.cn/showproblem.php?pid=2688
posted on 2009-03-19 17:44
shǎ崽 閱讀(667)
評論(0) 編輯 收藏 引用