161. 2D Segment Tree & 2D Fenwick Tree

$2$D 세그먼트 트리($2$D Segment Tree)는 세그먼트 트리를 $2$차원으로 구성한 것이다. 즉 $1$차원 세그먼트 트리들이 여러 개 존재하고 여기서 같은 위치에 있는 노드들로 구성된 세그먼트 트리들이 추가로 존재하는 방식이다. 다음과 같이 $4 \times 4$ 크기의 테이블이 존재할 때 $2$차원 세그먼트 트리를 어떻게 구성하는지 알아보자.

A	B	C	D
E	F	G	H
I	J	K	L
M	N	O	P

$1$차원 세그먼트 트리를 구현할 때 $1$차원 배열을 선언했다. 비슷하게 $2$차원 세그먼트 트리를 $2$차원 배열로 구현할 것이다. 그러면 첫 번째 인덱스를 행, 두 번째 인덱스를 열에 대응해서 각 노드가 어느 범위의 데이터를 저장할지 결정할 수 있다.

첫 번째 인덱스로 다음과 같이 행 범위를 지정한다.

$a[1][]$

A	B	C	D
E	F	G	H
I	J	K	L
M	N	O	P

$a[2][]$

A	B	C	D
E	F	G	H
I	J	K	L
M	N	O	P

$a[3][]$

A	B	C	D
E	F	G	H
I	J	K	L
M	N	O	P

$a[4][]$

A	B	C	D
E	F	G	H
I	J	K	L
M	N	O	P

$a[5][]$

A	B	C	D
E	F	G	H
I	J	K	L
M	N	O	P

$a[6][]$

A	B	C	D
E	F	G	H
I	J	K	L
M	N	O	P

$a[7][]$

A	B	C	D
E	F	G	H
I	J	K	L
M	N	O	P

두 번째 인덱스로 다음과 같이 열 범위를 지정한다.

$a[][1]$

A	B	C	D
E	F	G	H
I	J	K	L
M	N	O	P

$a[][2]$

A	B	C	D
E	F	G	H
I	J	K	L
M	N	O	P

$a[][3]$

A	B	C	D
E	F	G	H
I	J	K	L
M	N	O	P

$a[][4]$

A	B	C	D
E	F	G	H
I	J	K	L
M	N	O	P

$a[][5]$

A	B	C	D
E	F	G	H
I	J	K	L
M	N	O	P

$a[][6]$

A	B	C	D
E	F	G	H
I	J	K	L
M	N	O	P

$a[][7]$

A	B	C	D
E	F	G	H
I	J	K	L
M	N	O	P

각 칸이 관리하는 범위는 해당하는 행과 열이 관리하는 부분의 교집합에 해당한다.

 

이렇게 세그먼트 트리를 구축한 다음 원소의 값이 변하면 그 원소를 포함하는 모든 노드의 값을 갱신하면 된다.

구현은 다음과 같다. 합 세그먼트 트리이다. 먼저 다음과 같이 초기화 코드를 작성하고,

int m, n, p = 1 << 10, l[1 << 11], r[1 << 11], a[1 << 11][1 << 11];

for(int i = 0; i < p; i++)l[p + i] = r[p + i] = i;
for(int i = p; --i;)
{
    l[i] = l[i << 1];
    r[i] = r[i << 1 | 1];
}

cin >> n >> m;
for(int i = 1; i <= n; i++)
{
    for(int j = 1; j <= m; j++)cin >> a[p + i][p + j];
    for(int j = p; --j;)a[p + i][j] = a[p + i][j << 1] + a[p + i][j << 1 | 1];
}
for(int i = p; --i;)
{
    for(int j = p + p; --p;)a[i][j] = a[i << 1][j] + a[i << 1 | 1][j];
}

원소들의 값을 갱신하는 코드를 작성하고,

void REP(int i, int j, int v) // i행 j열의 값을 v로 바꾼다.
{
    for(a[i += p][j += p] = v; i; i >>= 1)
    {
        if(i < p)a[i][j] = a[i << 1][j] + a[i << 1 | 1][j];
        for(int k = j; k >>= 1;)a[i][k] = a[i][k << 1] + a[i][k << 1 | 1];
    }
}

주어지는 구간의 합을 구하는 코드를 작성한다.

int getSum(int lx, int rx, int ly, int ry, int dx, int dy) // (lx, rx)번째 원소부터 (rx, ry)번째 원소까지의 합을 구해야 하고, 현재 탐색하는 노드가 (dx, dy)번인 경우
{
    if(lx > r[dx] || rx < l[dx])return 0;
    if(x <= l[d] && r[d] <= y)
    {
        if(ly > r[dy] || ry < l[dy])return 0;
        if(ly <= l[dy] && r[dy] <= ry)return a[dx][dy];
        return getSum(lx, rx, ly, ry, dx, dy << 1) + getSum(lx, rx, ly, ry, dx, dy << 1 | 1);
    }
    return getSum(lx, rx, ly, ry, dx << 1, dy) + getSum(lx, rx, ly, ry, dx << 1 | 1, dy);
}

 

$2$D 펜윅 트리($2$D Fenwick Tree)도 비슷한 원리로 작동한다. 자세한 설명은 현재는 생략한다. (추후 추가 예정)

 

어떤 의미로는 안타깝게도 $2$D 세그먼트 트리는 잘 사용되지 않는다. $2$D 세그먼트 트리의 사용을 의도한 문제들이 $2$D 세그먼트 트리 없이 풀리는 일이 자주 발생하기 때문인데, 당장 $2$D 세그먼트 트리의 가장 기본적인 문제 중 하나인 구간 합 구하기 3부터가 세그먼트 트리 없이 행별로 누적합을 구하는 풀이로 풀리는 것을 보면 알 수 있다. 그나마 $2$D 펜윅 트리는 속도가 매우 빠르다는 장점이 있어서 가끔씩 등장하는 편이다.

 

[연습문제]

 

BOJ 11658. 구간 합 구하기 3 (Platinum IV)

$2$D 세그먼트 트리를 사용하면 쉽게 풀리긴 하는데 앞에서도 언급했듯이 이거 없이도 쉽게 풀 수가 있다.

 

→ solved.ac tag: multi_segtree