세그먼트 트리 비츠는 레이지 세그먼트 트리와 세그먼트 트리에 대한 이해가 선행되어야 합니다. 아직 세그먼트 트리와 레이지 세그먼트 트리를 잘 모르신다면 [자료구조] 세그먼트 트리(Segmenmt Tree)와 [자료구조] 레이지 세그먼트 트리(Lazy Segmenmt Tree)를 먼저 읽고 오시는걸 추천합니다.
개요
레이지 세그먼트는 바로 업데이트가 필요 없는 부분은 과감히 가지치기해서 업데이트 시간을 줄였습니다. 하지만 업데이트가 한 문제에 여러 연산이 있는 경우와 같이 레이지 세그먼트 트리로도 풀기 어려운 문제들이 있습니다. 이런 문제들을 풀때 사용하는게 세그먼트 트리 비츠입니다.
레이지 세그먼트 트리?
세그먼트 트리 비츠는 쉽게 설명하면 레이지 세그먼트 트리에서 사용하는 가지치기 방법을 확장하여 한번에 여러 연산에도 적용이 가능하게 만듭니다.
(개념 자체가 복잡해서 정확한 이해는 못했지만, 저는 일단 이렇게 이해했습니다.)
세그먼트 트리 비츠는 문제에 따라서 가지치기 조건을 정하는게 달라지기 때문에 백준의 19277 - ADD, DIV, MAX 문제를 예시로 설명하겠습니다.
우선 문제에 대해 설명하겠습니다.
문제
문제 설명
수열 \(a_0, a_1, \dots, a_{N-1}\)이 주어진다.
여기에 대해 총 \(Q\)개의 쿼리를 수행해야 한다. 쿼리의 종류는 다음 세 가지이다.
- ADD t = 0, l, r, x : 구간 [l, r]의 모든 원소에 대해 \(a_i = a_i + x\)를 수행한다.
- DIV t = 1, l, r, x : 구간 [l, r]의 모든 원소에 대해 \(a_i = \lfloor \frac{a_i}{x} \rfloor\) 를 수행한다.
- MAX t = 2, l, r, x = 0 : 구간 [l, r] 내의 최댓값 \(\max(a_l, a_{l+1}, \dots, a_r)\)을 출력한다.
입력
다음과 같은 형태로 주어진다.
1
2
3
4
5
6
N Q
a0 a1 ... aN-1
t1 l1 r1 x1
t2 l2 r2 x2
...
tQ lQ rQ xQ
- \[1 \leq N, Q \leq 200{,}000\]
- \[0 \leq a_i \leq 10^8\]
- \[t_i \in \{0, 1, 2\}\]
- \[0 \leq l_i \leq r_i \leq N-1\]
- \[1 \leq x_i \leq 1000 if t_i \neq 2, and x_i = 0 if t_i = 2\]
출력
각 MAX 쿼리에 대해 최댓값을 한 줄에 하나씩 출력한다.
19277 문제는 값을 변경해야하는 쿼리가 ADD와 DIV로 두 종류 입니다. 지금까지 본 세그먼트 트리와 레이지 세그먼트 트리는 모두 값 변경에 대한 쿼리가 여러개면 구현하기 상당히 복잡하고 어려워 집니다. 어떤 방식으로 문제를 푸는지 개념에 대해 설명드리겠습니다.
문제 풀이 개념
각 연산에 대해 분석해 보겠습니다.
- ADD는 lazy로 간단히 처리가 가능할 것 같습니다.
- DIV는 ADD처럼 lazy로 처리가 불가능 합니다. 별도로 관리해 줘야 할 것 같습니다.
- MAX 쿼리는 구간 합을 저장하듯이 구간의 최댓값을 저장해두면 기존 방법을 응용하면 사용이 가능할 것 같습니다.
ADD와 MAX는 약간의 응용만 하면 쉽게 처리가 가능하지만, DIV가 세그먼트 트리로 처리하기 까다로워 보입니다. DIV는 어떻게 처리하는게 좋을까요?
몫만 구하는 연산의 특징을 생각해 봅시다. 몫은 나눠지는 수에 따라서 일정 구간 같은 값이 나올 수 있습니다. 예를들면 6, 7, 8로 구성된 배열이 있을때, 6으로 나누고 몫을 구한다면 모두 1, 1, 1로 변환됩니다. 이 특성을 이용해서 가지치기를 하면 됩니다.
트리 구성
위와같은 방법으로 가지치기를 하려면 최솟값과 최댓값을 저장해서 범위를 저장해 합니다. 최솟값과 최솟값을 DIV에 주어진 숫자로 나누어 몫을 구했을때 같은 숫자가 나온다면 그 노드의 자식 노드는 몫을 저장해두고 나중에 업데이트 해도 됩니다. 종합해보면 트리는 [최댓값, 최솟값, add lazy, div lazy]으로 구성됩니다.
초기화
위에서 설명한 구조로 초기화 하는 코드입니다. 몫의 범위는 음이 아닌 정수이기 때문에, div lazy에 값이 저장되지 않았을때를 -1로 정해서 초기화 했습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
# [max, min, add lazy, div lazy]
tree = [[0, 0, 0, -1] for _ in range(n * 4)]
def init(node, left, right):
if left == right:
tree[node] = [data[left - 1], data[left - 1], 0, -1]
return
mid = (left + right) // 2
init(node * 2, left, mid)
init(node * 2 + 1, mid + 1, right)
tree[node][0] = max(tree[node * 2][0], tree[node * 2 + 1][0])
tree[node][1] = min(tree[node * 2][1], tree[node * 2 + 1][1])
ADD
ADD는 기존 레이지 방식대로 구현하면 됩니다. 조금 다른점은 최솟값과 최대값에 값을 더한다는것 입니다. 구간 합을 하면 최댓값과 최솟값에도 동일한 값이 더해지기 때문입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def add(node, start, end, left, right, value):
propagate(node, left, right)
if end < left or right < start:
return
if start <= left and right <= end:
tree[node][2] += value
propagate(node, left, right)
return
mid = (left + right) // 2
add(node * 2, start, end, left, mid, value)
add(node * 2 + 1, start, end, mid + 1, right, value)
tree[node][0] = max(tree[node * 2][0], tree[node * 2 + 1][0])
tree[node][1] = min(tree[node * 2][1], tree[node * 2 + 1][1])
DIV
DIV도 ADD와 같이 범위 찾는 작업은 동일하게 진행합니다. 범위 내에 포홤될 때 경우의 수를 나누면 세 가지 경우가 있습니다.
최대-최소의 결과값이 같을경우
div lazy에 몫을 저장해두고 추후에 반영합니다.
max == min + 1 인 경우
이 경우 DIV 연산을 ADD 연산으로 바꾸어 시간을 절약할 수 있습니다.
max == min + 1이 만족하면 DIV 연산을 수행했을때 두 가지 경우가 생깁니다.
min의 몫을 a, max의 몫을 b라고 할때, a == b 이거나 a + 1 == b가 성립합니다.
그런데 a == b인 경우에는 이미 위에서 처리가 되었으므로, 실제로는 a + 1 == b인 경우만 남게됩니다.
기존 max-min과 b - a가 모두 1로 같습니다.
이는 b - mi을 구해 max에 더해주면 똑같은 몫을 구했을때와 같은 결과가 나온다는 뜻입니다.
그래서 add lazy에 min % value - min을 저장해두고 반영하면 됩니다.
코드로 구현하면 다음과 같습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def div(node, start, end, left, right, value):
propagate(node, left, right)
if end < left or right < start or value == 1:
return
if start <= left and right <= end:
if tree[node][0] // value == tree[node][1] // value:
tree[node][3] = tree[node][0] // value
propagate(node, left, right)
return
if tree[node][0] == tree[node][1] + 1:
tree[node][2] += tree[node][1] // value - tree[node][1]
propagate(node, left, right)
return
mid = (left + right) // 2
div(node * 2, start, end, left, mid, value)
div(node * 2 + 1, start, end, mid + 1, right, value)
tree[node][0] = max(tree[node * 2][0], tree[node * 2 + 1][0])
tree[node][1] = min(tree[node * 2][1], tree[node * 2 + 1][1])
propagate
각 lazy에 저장한 값을 반영하는 함수 역시 작성해야 합니다. 기존 레이지 세그먼트는 전파 단계가 하나였지만, 이번에는 DIV, ADD 총 두 단계를 거처야 합니다.
DIV는 ADD한 값을 덮어씌우는 성질이 있기 때문에 먼저 수행되어야 합니다. 만약 DIV 후 ADD에 저장된 값이 남아있다면 그대로 반영하면 됩니다. 아래 함수에서는 추가로 DIV와 ADD 모두 저장된 값이 있다면 DIV lazy값에 ADD lazy값을 미리 더해서 실행 시간을 조금이라도 줄이게 했습니다.
코드로 구현하면 다음과 같습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def propagate(node, left, right):
if tree[node][3] >= 0 and tree[node][2] != 0:
tree[node][3] += tree[node][2]
tree[node][2] = 0
if tree[node][3] >= 0:
tree[node][0] = tree[node][3]
tree[node][1] = tree[node][3]
if left != right:
tree[node * 2][3] = tree[node][3]
tree[node * 2 + 1][3] = tree[node][3]
tree[node * 2][2] = 0
tree[node * 2 + 1][2] = 0
tree[node][3] = -1
if tree[node][2] == 0:
return
tree[node][0] += tree[node][2]
tree[node][1] += tree[node][2]
if left != right:
tree[node * 2][2] += tree[node][2]
tree[node * 2 + 1][2] += tree[node][2]
tree[node][2] = 0
MAX
MAX는 저장해둔 MAX 값을 범위를 찾아 가져오면 됩니다. 기존 방식과 크게 달라진 부분이 없습니다.
1
2
3
4
5
6
7
8
9
def max_range(node, start, end, left, right):
propagate(node, left, right)
if left > end or right < start:
return 0
if start <= left and right <= end:
return tree[node][0]
mid = (left + right) // 2
return max(max_range(node * 2, start, end, left, mid),
max_range(node * 2 + 1, start, end, mid + 1, right))
이렇게 문제의 쿼리에 따라 효율적으로 가지치기가 가능한 부분을 찾아 시간을 줄일 수 있게 만드는 세그먼트 트리를 세그먼트 트리 비츠라고 합니다. 예시로 든 문제에서 알 수 있듯이 상당히 고난이도 문제에 자주 사용됩니다. 그래도 문제를 풀고나면 참신한 풀이법 때문에 재밌는것 같습니다. 개념 자체는 이해하기 크게 어렵지 않으니 한번 도전해보시기 바랍니다.