[백준] 11658 구간 합 구하기 3

2차원 펜윅트리로 풀 수 있는 문제다.

펜윅트리를 2차원으로 생각하면 x축으로 펜윅트리가 있고 

그 x축을 가진 y축 펜윅트리가 있다고 생각하면 편하다

업데이트와 합을 구할 때는 2중 포문으로 

x축을 먼저 업데이트 해주고 

그에 맞게 y축을 업데이트 해주면 된다

(a,b) ~ (x,y) 에 대한 합을 구하는건 그림을 그려보면 이해하기 쉽다

(x,y) 까지의 합에서  - (a-1,y) - (x,b-1) + (a-1,b-1)을 하면

원하는 구간이 나온다!

그림으로 색칠해보는 것이 이해하기 쉬운 것 같다

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <map>
#include <cstring>
#include <string>
using namespace std;
int tree[1111][1111];
int n, m;
 
int sum(int x, int y) {
    int ret = 0;
    for (int i = x; i > 0; i -= (i&-i)) {
        for (int j = y; j > 0; j -= (j&-j)) {
            ret += tree[i][j];
        }
    }
    return ret;
}
 
void update(int x, int y, int val) {
    for (int i = x; i <= n; i += (i&-i)) {
        for (int j = y; j <= n; j += (j&-j)) {
            tree[i][j] += val;
        }
    }
}
int main() {
    scanf(" %d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int x; scanf(" %d", &x);
            update(i, j, x);
        }
    }
    for (int i = 0; i < m; i++) {
        int c; scanf(" %d", &c);
        if (c == 0) {
            int x, y, z; scanf(" %d %d %d", &x, &y, &z);
            int def = sum(x, y) - sum(x - 1, y) - sum(x, y - 1) + sum(x - 1, y - 1);
            update(x, y, z-def);
        }
        else {
            int a, b, x, y; scanf(" %d %d %d %d", &a, &b, &x, &y);
            printf("%d\n", sum(x, y)-sum(a-1,y) - sum(x,b-1) + sum(a-1,b-1));
        }
    }
}