구간 합 구하기 3( BOJ 11658 )

문제

11658. 구간 합 구하기 3 : https://www.acmicpc.net/problem/11658

11658번: 구간 합 구하기 3

 

문제 이해하기

• 2차원 표에서 구간의 합을 구해야 합니다.
• 합을 구하는 문제이기 때문에 펜윅트리를 사용할 수 있습니다.
• 하지만 1차원 배열을 활용한 펜윅트리로는 제한된 시간 안에 해결할 수 없습니다.
• 데이터가 2차원 표이기 때문에 제한시간 내 해결하기 위해서는 2차원 펜윅트리(2D 펜윅트리)를 만들어야 합니다.

 

문제 해결하기

• 2D 펜윅트리에서의 갱신은 1차원 펜윅트리와 유사합니다. 차이점은 2차원으로 처리한다는 점입니다.
• 각 행에 대해 열을 계속 갱신하면 됩니다. >> 중첩 반복문을 사용합니다.
  예를 들어, 표에서 (i, j)의 값을 갱신하면 i의 값이 n보다 커지기 전까지 j를 계속 갱신하면 됩니다.
• 2D 펜윅트리에서의 탐색 또한 갱신과 동일합니다. 각 행에 대해 열의 값을 모두 탐색하면 됩니다.
  다만, (x1, y1) ~ (x2, y2)의 값을 구하기 위해서는 2차원 배열에서의 구간 합 방식을 사용해야 합니다.

 

#include <stdio.h>
#include <vector>
#define NMAX 1050
#define SWAP(a,b,t) (t=a,a=b,b=t)
 
// input
int n, m;
int op, x1, y1, x2, y2, c;
int inp[NMAX][NMAX];
 
// 2D Fenwick Tree
int sz, t;
int BIT[NMAX][NMAX];
 
// result
int ret;
std::vector< int > ans;
 
 
void update(int x, int y, int val) {
    int pos;
 
    // 2D Fenwick Tree
    while(x<=n) {
        pos = y;
        while(pos<=n) {
            BIT[x][pos] += val;
 
            pos += (pos & -pos);
        }
 
        x += (x & -x);
    }
}
 
 
int search(int x, int y) {
    int pos, ret;
 
    // 2D Fenwick Tree
    ret = 0;
    while(x>0) {
        pos = y;
        while(pos>0) {
            ret += BIT[x][pos];
 
            pos -= (pos & -pos);
        }
 
        x -= (x & -x);
    }
 
    return ret;
}
 
 
int main() {
    scanf("%d %d", &n, &m);
 
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            scanf("%d", &inp[i][j]);
 
            update(i, j, inp[i][j]);
        }
    }
 
    for(int q=1;q<=m;q++) {
        scanf("%d", &op);
 
        switch(op) {
            case 0:
                scanf("%d %d %d", &x1, &y1, &c);
                
                update(x1, y1, c-inp[x1][y1]);
                inp[x1][y1] = c;
 
                break;
 
            default:
                scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
 
                ret = search(x2, y2) - search(x2, y1-1) - search(x1-1, y2) + search(x1-1, y1-1);
 
                ans.push_back(ret);
                
        }
    }
 
    for(int val:ans) printf("%d\n", val);
}

 

후기

2차원 펜윅트리를 직접 배워볼 수 있는 기회가 되었습니다. 펜윅트리에 능숙해진 후에 문제를 풀어보면 좋을듯 합니다.

 

 

참고 자료

- 펜윅 트리 : www.acmicpc.net/blog/view/21

펜윅 트리 (바이너리 인덱스 트리)

- 2D 펜윅 트리 : www.quora.com/How-do-I-implement-a-2D-binary-indexed-tree-for-range-update-and-range-query-operations

How do I implement a 2D binary indexed tree for range update and range query operations?