BOJ 11658

16 Feb 2020 • ProblemSolving

구간합구하기 3

문제출처

문제 해석

  • NxN표 안에 어떤 구간의 합을 구하는 문제입니다.
  • N <= 1024, M <= 100,000

설계(10)

  • 구간합구하기 문제의 심화버전입니다. 일전에는 1차원 배열의 구간합을 구하는 문제였으나, 이번에는 2차원 배열의 구간합을 구해야 합니다.
  • 세그먼트 트리 또는 BIT를 사용하여 해결할 수 있으나, 세그먼트 트리는 세그트리의 세그트리를 만드는 과정이 실제로 어떻게 구현을 해야할지 감이 잡히지 않고, 다른분들의 블로그를 찾아봐도 너무나도 난해하여 BIT를 사용하기로 하였습니다.
  • 2차원 BIT를 사용하면 2차원 구간합 문제를 해결할 수 있습니다.
  • 모든 수에 대해 업데이트를 진행하고, (x1,y1),(x2,y2)의 구간합을 구할 때 sum(x2,y2)-sum(x1-1,y2) - sum(x2,y1-1)+sum(x1-1,y1-1)를 하면 된다는 것을 알면 쉽게 구할 수 있습니다.

구현(30)

코드
#include <iostream>
using namespace std;
#define MAXN 1025

int tree[MAXN][MAXN];
int arr[MAXN][MAXN];
int N,M;
void update(int x, int y, int num){

    for (int i = x; i<= N; i+= (i&-i)){
        for (int j = y; j<=N; j+= (j&-j)){
            tree[i][j] += num;
        }
    }
}
int sum(int x, int y){
    int ans = 0;
    for (int i = x; i > 0; i-=(i&-i)){
        for (int j = y; j>0; j-= (j&-j)){
            ans += tree[i][j];
        }
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    for (int i =1 ; i <=N; i++){
        for (int j=1; j<=N; j++){
            cin >> arr[i][j];
            update(i,j,arr[i][j]);
        }
    }
    while (M--){
        int w;
        cin >>  w;
        if (w ==0){
            int x,y,c;
            cin >> x >> y >> c;
            int diff = c - arr[x][y];
            update(x,y,diff);
            arr[x][y] = c;
        }
        else{
            int x1,y1,x2,y2;
            cin >> x1 >> y1 >> x2 >> y2;
            cout << sum(x2,y2) - sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)<<"\n";
        }
    }
    return 0;
}
디버깅
  • sum함수를 구현할 때 i와 j의 탐색범위를 0까지 조사하도록 잘못구현하였습니다.
제출결과
  • 196ms

마무리

  • 2차원배열의 구간합을 구하는 문제였습니다. 세그먼트트리를 이용하여 2차원 배열의 구간합을 구하고자 하였으나 그러지 못하고, 구현이 세그트리에 비해 간단한 BIT를 이용하여 문제를 해결하였습니다.
  • 세그트리 알고리즘을 더욱 연습해봐야 할 것 같습니다.
 BOJ

Related Posts