백준 11658번 구간 합 구하기 3 문제풀이(C++)

백준 11658번 구간 합 구하기 3

아이디어

중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다.
-> 값 업데이트 + 구간합 = 펜윅트리

근데 표로 표현?? -> 2차원 배열로 똑같이 상관없이

단// (r2, c2)까지의 합을 구할때 (r2, c1-1), (r1-1,c2)각 모서리를 빼주고 중복으로 뺀 (r1-1, c1-1)을 더해주어야 한다!!

문제풀이

#include<bits/stdc++.h>
using namespace std;
#define MAX 1030
int n, m;
int table[MAX][MAX];
int tree[MAX][MAX];
void update(int r, int c, int num) {
    int tmp = c;
    while(r<= n + 1){
        while(tmp <= n + 1){
            tree[r][tmp] += num;
            tmp += (tmp & -tmp);
        }
        tmp = c;
        r += (r & -r);
    }

}
int sum(int r, int c) {
    int res = 0, tmp = c;
    while(r){
        while(tmp){
            res += tree[r][tmp];
            tmp -= (tmp & -tmp);
        }
        tmp = c;
        r -= (r & -r);
    }
    return res;
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> table[i][j];
            update(i, j, table[i][j]);
        }
    }
    int w, r1, c1, r2, c2, num;
    while (m--) {
        cin >> w;
        if (w == 0) {
            cin >> r1 >> c1 >> num;
            update(r1, c1, num - table[r1][c1]);
            table[r1][c1] = num;
        }
        else {
            cin >> r1 >> c1 >> r2 >> c2;
            cout << sum(r2, c2) - sum(r2, c1 - 1) 
                - sum(r1 - 1, c2) + sum(r1 - 1, c1 - 1) << '\n';
        }
    }
    return 0;
}