[BOJ 11658]구간 합 구하기3

[BOJ 11658]구간 합 구하기3 - P5

문제 설명

2차원 grid에서 LeftTop의 좌표 ~ RightBottom의 좌표 사이에 있는 직사각형 형태 안에 포함된 숫자들 모두 더해서 값을 구하거나, 업데이트를 하는 쿼리를 수행한다.

문제 풀이

2차원 세그먼트 트리를 만든다. 기존 세그먼트 트리(1차원) 각각의 노드마다 또다른 세그먼트 트리를 매다는 형태이다. 가로(좌우)형태의 세그 트리를 main으로 짜고 곁가지로 세로(상하)형태의 트리가 달려있다고 생각하면 편하다.

소스 코드

#include<stdio.h>
#include<algorithm>
#include<vector>
typedef long long ll;
using namespace std;
const int SIZE = 1030;
int tree[SIZE*4][SIZE*4];
int arr[SIZE][SIZE];
int startIdx = 1;

int makeRTree(int nodeR,int nodeC){
    if(nodeR >= startIdx) return tree[nodeR][nodeC];

    return tree[nodeR][nodeC] = makeRTree(nodeR*2,nodeC) + makeRTree(nodeR*2+1,nodeC);
}

int makeCTree(int nodeR,int nodeC){
    if(nodeC >= startIdx) return makeRTree(nodeR,nodeC);

    return tree[nodeR][nodeC] = makeCTree(nodeR,nodeC*2) + makeCTree(nodeR,nodeC*2+1);
}

int getRSum(int nodeR,int nodeC,int cr1,int cr2,int qr1,int qr2){
    if(cr1 > qr2 || qr1 > cr2) return 0;
    if(qr2 >= cr2 && cr1 >= qr1) return tree[nodeR][nodeC];

    int mid = (cr1 + cr2)/2;
    return getRSum(nodeR*2,nodeC,cr1,mid,qr1,qr2) + getRSum(nodeR*2+1,nodeC,mid+1,cr2,qr1,qr2);
}

int getCSum(int node,int cc1,int cc2,int qr1,int qc1,int qr2,int qc2){
    if(cc1 > qc2 || qc1 > cc2) return 0;
    if(qc2 >= cc2 && cc1 >= qc1) return getRSum(1,node,1,startIdx,qr1,qr2);

    int mid = (cc1 + cc2)/2;
    return getCSum(node*2,cc1,mid,qr1,qc1,qr2,qc2) + getCSum(node*2+1,mid+1,cc2,qr1,qc1,qr2,qc2);
}

void update(int r,int c,int x){
    r = startIdx + r - 1, c = startIdx + c - 1;
    tree[r][c] = x;

    for(int i=r ; i>=1 ; i/=2){
        for(int j=c ; j>=1 ; j/=2){
            if(i==r && j==c) tree[i][j] = x;
            else tree[i][j] = max(tree[i*2][j] + tree[i*2+1][j], tree[i][j*2] + tree[i][j*2+1]);
        }
    }

}

int main(){
    int n,q;    scanf("%d %d",&n,&q);
    for(;startIdx < n ; startIdx *= 2);

    for(int i=1 ; i<=n ; i++){
        for(int j=1 ; j<=n ; j++){
            scanf("%d",&arr[i][j]);
            tree[startIdx + i - 1][startIdx + j - 1] = arr[i][j];
        }
    }

    for(int i=1 ; i<=startIdx*2 ; i++)
        makeCTree(i,1);

    while(q--){
        int cmd;    scanf("%d",&cmd);

        if(cmd == 0){
            int r,c,x;  scanf("%d %d %d",&r,&c,&x);
            update(r,c,x);
        }
        else{
            int r1,c1,r2,c2;    scanf("%d %d %d %d",&r1,&c1,&r2,&c2);
            printf("%d\n",getCSum(1,1,startIdx,r1,c1,r2,c2));
        }
    }
    return 0;
}