一维情况：
设序列的元素存储在a[]中，a的下标是1..n的正整数，需要动态地更新某个a[x]的值，同时要求出a[x1]到a[y1]这一段所有元素的和。
如果要动态更新m次。。我们显然可以用o(mn)的暴力弄出来
其实可以o(mlogn)的；
在李睿的论文里提出了一种新的数据结构：
很巧妙，很强大：
对于序列a[]，我们设一个数组C，其中 （k为i在二进制下末尾0的个数）。
c[i]=a[i]+a[i-1]+...+
a[i-2^k+1]//这一项的最后一位一定是0
包含a[x]的c序列：
c[x]=a[x]+a[x-1]+...+a[x-2^k+1]
c[x+2^k]=a[x+2^k]+a[x+2^k-1]...+a[x]+...+a[x-2^k+1]
....
一直加到<=S的状况
针对这个情况。。我们有两个实现。。一个是update(),另一个是统计的操作
如果针对上面的统计就是求给定区间的sum （x,y）=sum(1,y)-sum(1,x)；
procedure UPDATA(x,A)
begin
p←x
while (p<=n) do
begin
C[p]←C[p]+A
p←p+LOWBIT(p)
end
end
求a[1]-a[x]的和
function SUM(x)
begin
ans ← 0
p ← x
while (p>0) do
begin
ans←ans+C[p]
p←p-LOWBIT(p)
end
return ans
end
我们通过一维的可以扩展成二维的：（IOI
MOBILES）
以下是我的这代码：
#include<iostream>
#define MaxS 1025
#define L(a) (a&(a^(a-1)))
int S,x,y,A,L,B,R,T;
int c[MaxS][MaxS];
void update()
{
//x<=i<S的c[i][y]更新
int i,j;
for(i=x;i<=S;i+=L(i))
for(j=y;j<=S;j+=L(j))
c[i][j]+=A;
}
int compute(int x,int y)
{
int result=0,i,j;
for(i=x;i>0;i-=L(i))
for(j=y;j>0;j-=L(j))
result+=c[i][j];
return result;
}
int main()
{
int oper,ans;
while(scanf("%d",&oper)&&oper!=3)
{
switch (oper)
{
case 0:
scanf("%d",&S);
memset(c,0,sizeof(c));
break;
case 1:
scanf("%d%d%d",&x,&y,&A);
x++,y++;
update();
break;
case 2:
scanf("%d%d%d%d",&L,&B,&R,&T);
L++,B++,R++,T++;
ans=compute(R,T)-compute(L-1,T)-compute(R,B-1)+compute(L-1,B-1);
printf("%d\n",ans);
break;
}
}
return 0;
}posted on 2008-07-13 19:40
zoyi 阅读(275)
评论(0) 编辑 收藏 引用 所属分类:
acm 、
数据结构