BOJ 11658 구간 합 구하기 3

일차원부터 짧게 언급해 둔다.

 

원래 수열을 arr 이라 하자.

 

통상적인 구현에서 segment tree 1 번은 arr 전체를 관리하고, 2 번은 좌측 절반, 3 번은 우측 절반, ...

 

이런 식으로 segment tree 의 각 원소는 원래 수열의 일정 범위를 관리하는 node 라는 사실은 2 차원이던 3차원이던 변함없다.

 

즉, tree[2][3] 은 앞의 절반의 행에 관한 정보와 뒤의 절반에 해당되는 원래 수열의 원소들에 관한 정보를 가진다.

 

tree[2][4] 는? 행에 관해서는 앞의 절반 그리고 열에 대해서는 첫 4분 구간에 대한 정보를 가질 것이다.

 

뭐 code 는 복잡해졌지만 위의 내용만 염두에 두면 번거롭기는 하지만 논리적으로 어렵지는 않다.

 

아래 구현에서는 i, y 가 행을 나타내고, j, x 가 열을 나타낸다.

 

#include<bits/stdc++.h>

using namespace std;

int arr[1025][1025];

int sz=1;
vector<vector<int>> tree;

void upd(int y, int x, int v) {
    int i=sz+y-1, j=sz+x-1;
    
    tree[i][j]=v;
    for(j>>=1;j>0;j>>=1) {
        tree[i][j]=tree[i][2*j]+tree[i][2*j+1];
    }
    
    for(i>>=1;i>0;i>>=1){
        j=sz+x-1;
        tree[i][j]=tree[2*i][j]+tree[2*i+1][j];
        for(j>>=1;j>0;j>>=1) {
            tree[i][j]=tree[i][2*j]+tree[i][2*j+1];
        }
    }
}

int xqry(int yNode, int tl, int tr, int xNode, int xl, int xr) {
    if(xr<tl || tr<xl) return 0;
    if(xl<=tl && tr<=xr) return tree[yNode][xNode];
    int mid=tl+tr>>1;
    return xqry(yNode, tl,mid,2*xNode,xl,xr)+xqry(yNode,mid+1,tr,2*xNode+1,xl,xr);
}

int yqry(int tl, int tr,int yNode, int yl, int yr, int xl, int xr) {
    if(yr<tl || tr<yl) return 0;
    if(yl<=tl and tr<=yr) return xqry(yNode, 1,sz,1,xl,xr);
    int mid=tl+tr>>1;
    return yqry(tl,mid,2*yNode,yl,yr,xl,xr)+yqry(mid+1,tr,2*yNode+1,yl,yr,xl,xr);
}

int main(){
    int n,m; scanf("%d%d",&n,&m);
    for(;sz<n;sz<<=1);
    tree=vector<vector<int>>(2*sz, vector<int>(2*sz, 0));
    
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) scanf("%d", &arr[i][j]), upd(i,j,arr[i][j]);
    
    for(int i=1;i<=m;i++) {
        int w; scanf("%d", &w);
        if(w==0){
            int x,y,c; scanf("%d%d%d",&x,&y,&c);
            upd(x,y,c);
        } else {
            int yl,xl,yr,xr; scanf("%d%d%d%d",&yl,&xl,&yr,&xr);
            printf("%d\n",yqry(1,sz,1,yl,yr,xl,xr));
        }
    }
}

 

어떻게 하면 변수명을 덜 헷갈리게 만들 수 있을까?

 

이왕 하는 거 Fenwick tree 를 사용한 기록해 둔다.

 

확실히 짧아서 좋다.

 

#include<cstdio>
int n, m;
int arr[1025][1025], bit[1025][1025];

void upd(int y, int x, int s) {
    for (; y<=n; y+=y&-y)
        for (int j=x; j<=n; j+=j&-j) 
            bit[y][j] += s;
}

int sum(int y, int x) {
    int s=0;
    for (; y>0; y&=y-1)
        for (int j=x; j>0; j&=j-1) 
            s += bit[y][j];
    return s;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i=1; i <= n; i++)
        for (int j=1; j <= n; j++) 
            scanf("%d", arr[i] + j), upd(i, j, arr[i][j]);
    
    for (int i=0; i < m; i++) {
        int w; scanf("%d", &w);
        if(w==0){
            int a,b,c; scanf("%d%d%d", &a,&b,&c);
            upd(a,b,c-arr[a][b]);
            arr[a][b]=c;
        } else {
            int yl,xl,yr,xr;
            scanf("%d%d%d%d", &yl,&xl,&yr,&xr);
            printf("%d\n", sum(yr, xr)-sum(yl-1,xr)-sum(yr, xl-1)+sum(yl-1, xl-1));
        }
    }
    return 0;
}