백준 11658번: 구간 합 구하기 3 (C++)

접근

https://www.acmicpc.net/problem/11658

11658번: 구간 합 구하기 3

세그먼트 트리의 응용 알고리즘인 펜윅 트리 알고리즘을 이용하여 문제를 해결하였다.

펜윅 트리가 무엇인지 아주 자세히 설명해놓은 글이 있어 링크를 남긴다.

https://yabmoons.tistory.com/438

[ 펜윅트리(FenwickTree) ] 개념과 구현방법 (C++)

본문에서는 1차원의 펜윅 트리 알고리즘을 설명하는데 아주 잘 이해가 되었다. 이를 N * N 배열에 적용하여 2차원 펜윅 트리를 만들어 구간 합 문제를 해결하였다.

1차원 펜윅 트리에서 Sum 1부터 idx 까지의 합을 리턴하게 되어 x1 부터 x2 까지의 구간 합을 구하기 위해서는 ( 1부터 x2 까지의 구간 합 ) - ( 1부터 x1 - 1 까지의 구간 합 ) 을 계산하여 답을 도출한다.

2차원의 펜윅 트리에서의 Sum 함수는 (1, 1) 에서부터 (x, y) 까지의 구간합을 구해준다. 따라서 (x1, y1) 부터 (x2, y2) 까지의 구간 합을 구하기 위해서는 ( (x2, y2) 까지의 구간 합 ) - ( (x2, y1 - 1) 까지의 구간 합 ) - ( (x1 - 1, y2) 까지의 구간 합 ) + ( (x1 - 1, y1 - 1) 까지의 구간합 ) 을 계산하여 원하는 구간 합을 구할 수 있다.

코드

#include <iostream>

using namespace std;

#define endl '\n'
#define MAX_N 1025

int N, M;
int MAP[MAX_N][MAX_N];
int tree[MAX_N][MAX_N];

void Update(int r, int c, int value) {
    int row = r;
    while (row <= N) {
        int col = c;
        while (col <= N) {
            tree[row][col] += value;
            col = col + (col & -col);
        }
        row = row + (row & -row);
    }
}

int Sum(int r, int c) {
    int res = 0;
    int row = r;
    while (0 < row) {
        int col = c;
        while (0 < col) {
            res += tree[row][col];
            col = col - (col & -col);
        }
        row = row - (row & -row);
    }
    return res;
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::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 >> MAP[i][j];
            Update(i, j, MAP[i][j]);
        }
    }
    for (int i = 0; i < M; i++) {
        int w;
        cin >> w;
        if (w == 0) {
            // Update
            int x, y, c;
            cin >> x >> y >> c;
            Update(x, y, c - MAP[x][y]);
            MAP[x][y] = c;
        } else {
            // GetSum
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            cout << Sum(x2, y2) - Sum(x2, y1 - 1) - Sum(x1 - 1, y2) + Sum(x1 - 1, y1 - 1) << endl;
        }
    }

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!