|Vijos|树状数组|P1512 SuperBrother打鼹鼠

https://vijos.org/p/1512

一个二维树状数组，注意树状数组不能出现0，把所有坐标+1即可，求子矩阵和为

sub(x2,y2) - sub(x1-1,y2) - sub(x2, y1-1) + sub(x1-1,y1-1) 其中sub为(1,1)到(x,y)矩阵的和。 #include<cstdio> #include<cstring> #include<algorithm> #define ms(i,j) memset(i, j, sizeof(i)); using namespace std; const int maxn = 1024 + 10; int n; int sum[maxn][maxn]; int lowbit(int x) {return x&(-x); } void add(int x, int y, int num) {int i,j;for (i=x; i <= maxn; i += lowbit(i)){for (j=y; j <= maxn; j += lowbit(j)){sum[i][j] += num;}} } int sub(int x, int y) {int ret = 0;int i,j;for (i=x; i > 0; i -= lowbit(i)){for (j=y; j > 0; j -= lowbit(j)){ret += sum[i][j];}}return ret; }int main () { scanf("%d", &n);int m;scanf("%d",&m);while (m!=3){if (m==1){int x,y,k;scanf("%d%d%d", &x, &y, &k);add(x+1,y+1,k);}if (m==2){int x1,y1,x2,y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);x1++, x2++, y1++, y2++;int u = sub(x2,y2) - sub(x1-1,y2) - sub(x2, y1-1) + sub(x1-1,y1-1);printf("%d\n", u);}scanf("%d",&m);}return 0; }

转载于:https://www.cnblogs.com/flyinthesky1/p/6384326.html

总结

以上是生活随笔为你收集整理的|Vijos|树状数组|P1512 SuperBrother打鼹鼠的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。