POJ1195——Mobile phones（二维树状数组）

本文主要是介绍POJ1195——Mobile phones（二维树状数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二维树状数组的模板题

有几种操作：

0 S 新建一个S*S的表

1 X Y A 在 （0，0）到（X,Y）内的元素+A

2 L B R T 询问  L<=x<=R , B<=y<=T  (x, y)区域的元素和 

3 结束

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#define INF 0x7fffffff
using namespace std;
int a[1030][1030];
int n;
int lowbit(int x)
{return x&(-x);
}
void add(int x,int y,int v)
{for(int i=x;i<=n;i+=lowbit(i))for(int j=y;j<=n;j+=lowbit(j))a[i][j]+=v;
}
int sum(int x,int y)
{int t=0;for(int i=x;i>0;i-=lowbit(i))for(int j=y;j>0;j-=lowbit(j))t+=a[i][j];return t;
}
int getsum(int x1,int y1,int x2,int y2)
{return sum(x2,y2)+sum(x1-1,y1-1)-sum(x1-1,y2)-sum(x2,y1-1);
}
int main()
{int c,x,y,v;while(~scanf("%d",&c)&&c!=3){if(c==0){memset(a,0,sizeof(a));scanf("%d",&n);}else if(c==1){scanf("%d%d%d",&x,&y,&v);add(x+1,y+1,v);}else if(c==2){int x1,x2,y1,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);printf("%d\n",getsum(x1+1,y1+1,x2+1,y2+1));}}return 0;
}

这篇关于POJ1195——Mobile phones（二维树状数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---