学步园

简单的一个二维树状数组的应用，没有变形

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1892

//二维树状数组<br /> //<br /> #include<stdio.h><br /> const int size = 1002;</p> <p>int C[size][size];<br /> int D[size][size];</p> <p>int lowbit(int n)<br /> {<br /> return n&(-n);<br /> }</p> <p>void Modify(int x, int y, int delta)<br /> {<br /> for(int i = x; i <= 1001; i += lowbit(i))<br /> for(int j = y; j <= 1001; j += lowbit(j))<br /> {<br /> C[i][j] += delta;<br /> }<br /> }</p> <p>int Sum(int i, int j)<br /> {<br /> //if(i<=0 || j<=0) return 0;</p> <p> int result = 0;<br /> for(int x = i; x > 0; x -= lowbit(x))<br /> {<br /> for(int y = j; y > 0; y -= lowbit(y))<br /> {<br /> result += C[x][y];<br /> }<br /> }</p> <p> return result;<br /> }</p> <p>int min(int x,int y)<br /> {<br /> return x<y?x:y;<br /> }</p> <p>int max(int x,int y)<br /> {<br /> return x>y?x:y;<br /> }</p> <p>int main()<br /> {<br /> int cas,q,ca;<br /> char str;<br /> int x1,y1,x2,y2,n1;<br /> int xmin,ymin,xmax,ymax;<br /> int ans;<br /> scanf("%d",&cas);<br /> for(ca = 1;ca <=cas;ca++)<br /> {<br /> printf("Case %d:/n",ca);<br /> //初始化<br /> for (x1 = 1;x1 <= 1001;x1++)<br /> for (y1 = 1;y1 <= 1001;y1++)<br /> {<br /> D[x1][y1] = 1;<br /> C[x1][y1] = lowbit(x1) * lowbit(y1);<br /> }<br /> scanf("%d",&q);<br /> while (q--)<br /> {<br /> getchar();<br /> scanf("%c",&str);<br /> if(str == 'S') //sum<br /> {<br /> scanf("%d %d %d %d",&x1,&y1,&x2,&y2);<br /> x1++;y1++;x2++;y2++;<br /> xmax = max(x1,x2);<br /> ymax = max(y1,y2);<br /> xmin = min(x1,x2);<br /> ymin = min(y1,y2);<br /> int temp = Sum(xmax,ymin-1) + Sum(xmin-1,ymax) - Sum(xmin-1,ymin-1);<br /> ans = Sum(xmax,ymax) - temp; //这样可以防止某些越界<br /> printf("%d/n",ans);<br /> }<br /> else if (str == 'A') //add<br /> {<br /> scanf("%d %d %d",&x1,&y1,&n1);<br /> x1++;y1++;<br /> Modify(x1,y1,n1);<br /> D[x1][y1] += n1;<br /> }<br /> else if (str == 'D') //delete<br /> {<br /> scanf("%d %d %d",&x1,&y1,&n1);<br /> x1++;y1++;<br /> if(D[x1][y1] < n1) n1 = D[x1][y1];<br /> Modify(x1,y1,-n1);<br /> D[x1][y1] -= n1;<br /> }<br /> else if (str == 'M') //move<br /> {<br /> scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&n1);<br /> x1++;y1++;x2++;y2++;<br /> if (n1 > D[x1][y1])<br /> n1 = D[x1][y1];<br /> D[x1][y1] -= n1;<br /> D[x2][y2] += n1;<br /> Modify(x1,y1,-n1);<br /> Modify(x2,y2,n1);<br /> }<br /> }<br /> }<br /> return 0;<br /> }</p> <p>/*<br /> 100<br /> 3<br /> S 1 1 1 1<br /> A 1 1 2<br /> S 1 1 1 1<br /> 3<br /> S 1 1 1 1<br /> A 1 1 2<br /> S 1 1 1 2<br /> */