POJ-1195-Mobile phones

深藏阁楼爱情的钟 2022-01-10 05:13 181阅读 0赞

### 链接：[https://vjudge.net/problem/POJ-1195][https_vjudge.net_problem_POJ-1195] ###

### 题意： ###

给一个S\*S的矩阵，有两种操作，给(x,y)位置增加一个值，和求一个内部矩形的和。

### 思路： ###

二维树状数组，先对每行来一个一维的树状数组，

再对行来一个树状数组

### 代码： ###

#include <iostream>
    #include <memory.h>
    #include <vector>
    #include <map>
    #include <algorithm>
    #include <cstdio>
    #include <math.h>
    #include <queue>
    #include <string>
    #include <stack>
    #include <iterator>
    #include <stdlib.h>
    #include <time.h>
    #include <assert.h>
    
    using namespace std;
    typedef long long LL;
    
    const int MAXN = 2000;
    int c[MAXN][MAXN];
    int n, op;
    
    int Lowbit(int x)
    {
        return x&(-x);
    }
    
    void Update(int x, int y, int v)
    {
        for (int i = x;i <= n;i += Lowbit(i))
        {
            for (int j = y;j <= n;j += Lowbit(j))
            {
                c[i][j] += v;
            }
        }
    }
    
    int Sum(int x, int y)
    {
        int res = 0;
        for (int i = x;i > 0;i -= Lowbit(i))
        {
            for (int j = y;j > 0;j -= Lowbit(j))
            {
                res += c[i][j];
            }
        }
        return res;
    }
    
    int main()
    {
        scanf("%d%d", &op, &n);
        while (~scanf("%d", &op))
        {
            if (op == 3)
                break;
            if (op == 1)
            {
                int x, y, v;
                scanf("%d%d%d", &x, &y, &v);
                x++, y++;
                Update(x, y, v);
            }
            if (op == 2)
            {
                int x1, y1, x2, y2;
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                x1++, y1++, x2++, y2++;
                printf("%d\n", Sum(x2, y2) - Sum(x1-1, y2) - Sum(x2, y1-1) + Sum(x1-1, y1-1));
            }
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/YDDDD/p/10700465.html

[https_vjudge.net_problem_POJ-1195]: https://vjudge.net/problem/POJ-1195