首页 > 代码库 > poj-1195
poj-1195
二维树状数组应用
http://poj.org/problem?id=1195
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <math.h> #include <stdlib.h> #include <vector> #include <queue> #include <map> #include <stack> using namespace std; int s; int p[1030][1030]; int lowbit(int x) { return x & -x; } void add(int a,int b,int d) { for (int i = a; i <= s; i += lowbit(i)) for (int j = b; j <= s; j += lowbit(j)) { p[i][j] += d; } } int sum(int a, int b) { int ans = 0; for (int i = a; i >0; i -= lowbit(i)) for (int j = b; j >0; j -= lowbit(j)) { ans += p[i][j]; } return ans; } void init(int s) { for (int i = 0; i <= s; i++) for (int j = 0; j <= s;j++) p[i][j] = 0; } int main() { int d; while (scanf("%d", &d) != EOF) { if (d == 3) return 0; if (d == 0) { scanf("%d", &s); init(s); } if (d == 1) { int x, y, a; scanf("%d %d %d", &x, &y, &a); { add(x + 1, y + 1, a); } } if (d == 2) { int l, b, r, t; scanf("%d %d %d %d", &l, &b, &r, &t); l++; b++; r++; t++; printf("%d\n", sum(l - 1, b - 1) + sum(r, t) - sum(r, b - 1) - sum(l - 1, t)); } } return 0; }
poj-1195
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。