一維情況：
設序列的元素存儲在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 閱讀(289)
評論(0) 編輯 收藏 引用 所屬分類:
acm 、
數據結構