POJ 1195 Mobile phones【树状数组二维】-蒲公英云

POJ 1195 Mobile phones【树状数组二维】

题目大意

更新：一个矩阵的一个元素
求和：求一个子矩阵元素和
学习了二维的树状数组
和一维一样 
只需要记住，对于矩阵A
C[i][j]的表示的是 
矩阵A[i][j]向左上分别延伸lowbit(i)和lowbit(j)个单位形成的子矩阵的和
#include <stdio.h>
#include <iostream>
using namespace std;
#pragma warning(disable:4996)
#define debug(x) cout<<#x<<": "<<(x)<<endl;
#define low(x) ((x)&(-x))
typedef long long ll;
//ll a[1025][1025];
ll c[1025][1025];
ll s;
bool update(ll x, ll y, ll A) { 
    for (ll i=x; i <= s; i += low(i)) { 
        for (ll j=y; j <= s; j += low(j)) { 
            c[i][j] += A;
        }
    }
    return true;
}
ll getS(ll x, ll y) { 
    ll ret = 0;
    for (ll i = x; i > 0 ; i -= low(i)) { 
        for (ll j = y; j > 0; j -= low(j)) { 
            ret += c[i][j];
        }
    }
    return ret;
}
int main() { 
    //freopen("../in1.txt","r",stdin);
    ll t;
    memset(c, 0, sizeof(c));
    while (cin >> t) { 
        if (t == 0) { 
            cin >> s;
        }
        else if (t == 1) { 
            ll x, y, A;
            cin >> x >> y >> A;
            update(x + 1, y + 1, A);
        }
        else if (t == 2) { 
            ll x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            //debug(getS(x2 + 1, y2 + 1))
            ll s = getS(x2+1,y2+1) - getS(x2+1,y1) - getS(x1,y2+1) + getS(x1,y1) ;
            cout << s << endl;
        }
    }
    return 0;
}