简单二维树状数组题。单点询问，两种更新（按行或者按列）。直接用二维的线段树，最多将更新的区间划分为3个。
代码如下：
View Code 1 #include2 #include 3 #include 4 5 using namespace std; 6 7 const int size = 105; 8 9 struct BIT2D { 10 int key[size][size]; 11 int row, col; // x-row y-col 12 13 void init() { 14 for (int i = 0; i <= row; i++) { 15 for (int j = 0; j <= col; j++) { 16 key[i][j] = 0; 17 } 18 } 19 } 20 21 void addMain(int x, int y, int k) { 22 if (!x || !y) return ; 23 for (int i = x; i > 0; i -= (-i) & i) { 24 for (int j = y; j > 0; j -= (-j) & j) { 25 key[i][j] += k; 26 } 27 } 28 } 29 30 void add(int x1, int y1, int x2, int y2, int k) { 31 addMain(x1 - 1, y1 - 1, k); 32 addMain(x1 - 1, y2, -k); 33 addMain(x2, y1 - 1, -k); 34 addMain(x2, y2, k); 35 } 36 37 int getPoint(int x, int y) { 38 int ret = 0; 39 40 for (int i = x; i <= row; i += (-i) & i) { 41 for (int j = y; j <= col; j += (-j) & j) { 42 ret += key[i][j]; 43 } 44 } 45 46 return ret; 47 } 48 } BIT; 49 50 void addCol(int x1, int y1, int x2, int y2, int k) { 51 if (x1 == x2) { 52 BIT.add(x1, y1, x2, y2, k); 53 } else { 54 BIT.add(x1, y1, x1, BIT.col, k); 55 if (x2 - x1 > 1) { 56 BIT.add(x1 + 1, 1, x2 - 1, BIT.col, k); 57 } 58 BIT.add(x2, 1, x2, y2, k); 59 } 60 } 61 62 void addRow(int x1, int y1, int x2, int y2, int k) { 63 if (y1 == y2) { 64 BIT.add(x1, y1, x2, y2, k); 65 } else { 66 BIT.add(x1, y1, BIT.row, y1, k); 67 if (y2 - y1 > 1) { 68 BIT.add(1, y1 + 1, BIT.row, y2 - 1, k); 69 } 70 BIT.add(1, y2, x2, y2, k); 71 } 72 } 73 74 int main() { 75 int Case = 1, m; 76 77 // freopen("in", "r", stdin); 78 while (~scanf("%d%d", &BIT.row, &BIT.col)) { 79 BIT.init(); 80 printf("Case %d\n", Case); 81 Case++; 82 for (int i = 1, x; i <= BIT.row; i++) { 83 for (int j = 1; j <= BIT.col; j++) { 84 scanf("%d", &x); 85 addRow(i, j, i, j, x); 86 } 87 } 88 /* 89 for (int i = 1; i <= BIT.row; i++) { 90 for (int j = 1; j <= BIT.col; j++) { 91 printf("%d ", BIT.getPoint(i, j)); 92 } 93 puts(""); 94 } 95 */ 96 scanf("%d", &m); 97 98 int op, a, b, c, d, e; 99 100 while (m--) {101 scanf("%d", &op);102 if (op == 0) {103 scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);104 if (a > c) {105 swap(a, c);106 swap(b, d);107 } else if (a == c && b > d) {108 swap(b, d);109 }110 addCol(a, b, c, d, e);111 } else if (op == 1) {112 scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);113 if (b > d) {114 swap(b, d);115 swap(a, c);116 } if (b == d && a > c) {117 swap(a, c);118 }119 addRow(a, b, c, d, e);120 } else {121 scanf("%d%d", &a, &b);122 printf("%d\n", BIT.getPoint(a, b));123 }124 /*125 for (int i = 1; i <= BIT.row; i++) {126 for (int j = 1; j <= BIT.col; j++) {127 printf("%d ", BIT.getPoint(i, j));128 }129 puts("");130 }131 */132 }133 }134 135 return 0;136 }
——written by Lyon