#寒假1# L - Mobile phones

题目

https://vjudge.net/problem/POJ-1195

思路

二维树状数组的模板题

代码

#include 
#include 
#include 
#include #define MAXX 1050
#define INF 0x3f3f3f3f
using namespace std;
int s;
int map[MAXX][MAXX];int lowbit(int x)
{return x & (-x);
}void update(int x, int y, int a)
{for(int i=x;i<=s;i+=lowbit(i))for(int j=y;j<=s;j+=lowbit(j))map[i][j]+=a;
}int add(int x, int y)  //从(1,1)到(x,y)
{int sum=0;for(int i=x;i>0;i-=lowbit(i))for(int j=y;j>0;j-=lowbit(j))sum+=map[i][j];return sum;}int main()
{int n;while (~scanf("%d", &n)){if (n == 0){cin >> s;memset(map, 0, sizeof map);} else if (n == 1){int x, y, a;scanf("%d%d%d", &x, &y, &a);update(x + 1, y + 1, a);} else if (n == 2){int l, b, r, t;scanf("%d%d%d%d", &l, &b, &r, &t);l++, b++, r++, t++;int sum = add(r, t) - add(r, b - 1) - add(l - 1, t) + add(l - 1, b - 1);printf("%d\n", sum);} elsebreak;}return 0;
}

注意

树状数组都是从1开始的，而这个题是从0开始的下标，所以要先把所给的数据进行+1操作，变成从1开始往后的才行，不然会超时

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！