中级农民
- 积分
- 126
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2015-4-22
- 最后登录
- 1970-1-1
|
这儿有一题,POJ1195。解法是二维树状数组,可以实现log(N) * log(N)时间的修改和求和。
我以前写的代码,其中树状数组的部分是关键代码:- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- using namespace std;
- const int MAXN = 1024;
- int c[MAXN + 1][MAXN + 1];
- int n;
- int low_bit(int x)
- {
- return x & (-x);
- }
- void add_value(int i, int j, int v, int n)
- {
- int j1;
- while(i <= n){
- j1 = j;
- while(j1 <= n){
- c[i][j1] += v;
- j1 += low_bit(j1);
- }
- i += low_bit(i);
- }
- }
- int get_sum(int i, int j)
- {
- int j1;
- int sum;
- if(i <= 0 || j <= 0){
- return 0;
- }
- sum = 0;
- while(i > 0){
- j1 = j;
- while(j1 > 0){
- sum += c[i][j1];
- j1 -= low_bit(j1);
- }
- i -= low_bit(i);
- }
- return sum;
- }
- int partial_sum(int x1, int y1, int x2, int y2)
- {
- return get_sum(x2, y2) + get_sum(x1 - 1, y1 - 1) - get_sum(x2, y1 - 1) - get_sum(x1 - 1, y2);
- }
- int main()
- {
- int op;
- int x1, y1, x2, y2, v;
- memset(c, 0, (MAXN + 1) * (MAXN + 1) * sizeof(int));
- while(scanf("%d", &op) == 1){
- if(op == 0){
- scanf("%d", &n);
- }else if(op == 1){
- scanf("%d%d%d", &x1, &y1, &v);
- ++x1;
- ++y1;
- add_value(x1, y1, v, n);
- }else if(op == 2){
- scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
- ++x1;
- ++y1;
- ++x2;
- ++y2;
- printf("%d\n", partial_sum(x1, y1, x2, y2));
- }else if(op == 3){
- break;
- }
- }
- return 0;
- }
复制代码 |
|