題意:要求設計這樣一個數據結構,支持下列操作
1.add(x,y,a).對二維數組的第x行,第y列加上a.
2.sum(l,b,r,t).求所有滿足l<=x<=r,b<=y<=t,的數組元素的和.
顯然,二維樹狀數組滿足這些要求.
poj1741，code:
var c:array[0..1025,0..1025] of longint;opt,n,x,y,a,l,b,r,t:longint;function lowbit(i:longint):longint;beginlowbit:=i and (i xor (i-1));end;procedure change(x0,y0,a:longint);var x,y:longint;beginx:=x0;while x<=n dobeginy:=y0;while y<=n dobegininc(c[x,y],a);inc(y,lowbit(y));end;inc(x,lowbit(x));end;end;function getsum(x0,y0:longint):longint;var x,y:longint;begingetsum:=0;x:=x0;while x>0 dobeginy:=y0;while y>0 dobegininc(getsum,c[x,y]);dec(y,lowbit(y));end;dec(x,lowbit(x));end;end;function query(x1,y1,x2,y2:longint):longint;beginexit(getsum(x2,y2)-getsum(x2,y1-1)-getsum(x1-1,y2)+getsum(x1-1,y1-1));end;beginreadln(opt,n);while opt<>3 dobeginread(opt);if opt=3 then halt;case opt of1:beginreadln(x,y,a);change(x+1,y+1,a);end;2:beginreadln(l,b,r,t);writeln(query(l+1,b+1,r+1,t+1));end;end;end;
end.
