세그먼트 트리의 Lazy Propagation + 파이썬 구현
- CS/자료구조
- 2021. 9. 22.
세그먼트 트리의 Lazy Propagation
이번 포스팅에서는 세그먼트 트리의 Lazy Propagation에 대해서 알아보겠습니다. Lazy Propagation은 구간 Query에 대한 시간 복잡도를 O(mnlogn)에서 O(nlogn) 수준으로 개선하는 방법입니다. 그 전에 세그먼트 트리 공부가 필요하신 부분은 아래 글 참고 부탁드립니다.
파이썬, 세그먼트 트리 구현
세그먼트 트리는 무엇인가? 세그먼트 트리는 완전이진트리를 기반으로 주워진 쿼리에 빠르게 응답하기 위해 만들어진 자료구조입니다. 제가 이 자료구조를 사용해서 문제를 풀었을 때는 대부
ojt90902.tistory.com
세그먼트 트리의 단점
세그먼트 트리는 기본적으로 특정 구간 내에 쿼리를 처리할 때, logn만에 처리할 수 있는 자료구조 형태입니다. 아래 그림은 세그먼트 트리가 특정 구간의 쿼리를 처리하는 것을 색깔로 표시한 그림입니다. 예를 들어, 아래 그림이 합을 나타낸 세그먼트 트리라고 하면, 2~3 구간의 합을 구하는데는 O(logn)이 필요합니다. 이 시간복잡도 덕분에 n의 값이 크면 클수록 세그먼트 트리의 구간 쿼리는 큰 효과를 보게 됩니다.
그렇지만 이 세그먼트 트리에도 한 가지 단점이 있습니다. 쿼리만 있는 세그먼트 트리라면 상관 없지만, 세그먼트 트리 내의 값이 업데이트 되는 상황이 있다고 하면 시간복잡도가 열화됩니다. 아래 그림을 예시로 들겠습니다.
최악의 경우 0~7의 구간 전부에서 인덱스를 바꿔야하는 경우가 있을 수 있습니다. 단일 노드의 값을 바꿀 때는 O(logn)의 시간이 걸렸지만, 구간의 값을 변경해야할 때는 최악의 경우 위처럼 O(nlogn)이 될 수 있습니다. 구간값 업데이트가 m번 반복되면 시간복잡도는 O(mnlogn)으로 원하는 시간 내에 쿼리가 진행되지 못할 수 있습니다.
Lazy Propagation란?
Segment Tree의 Lazy Propagation은 이런 단점을 보완하고자 나온 방안입니다. Lazy Propagation을 관통하는 생각은 '딱 필요한 노드까지만 업데이트를 진행한다. 그리고 나머지 노드들은 나중에 필요할 때, 다시 한번 업데이트 한다' 입니다. 아래 그림의 예시를 보면 좀 더 이해가 쉽습니다.
0~5번 구간에 대해서 특정 값을 업데이트 해야한다고 가정합니다. 왼쪽 그림은 기본적인 형태의 업데이트로 진행했을 때, 접근이 필요한 노드들을 연두색으로 표현했습니다. Lazy Progation으로 업데이트를 하면 오른쪽 그림으로 표현이 됩니다.
Lazy Propagation을 적용했을 때, 최악은 잎새노드 하나만 업데이트하는 경우이며 이 때 시간 복잡도는 O(logN)입니다. Lazy Propagation을 적용하면, m번의 update 쿼리가 들어왔을 때 O(mlogn)의 시간복잡도로 시간 내에 해결이 가능해집니다.
Lazy Propagation 구현
Lazy Propagation의 구현을 위해서 기본 세그먼트 트리와 달라지는 점은 크게 두 가지입니다. 먼저 아래 내용을 기억하면서 구현을 같이 한번 해보겠습니다
- 트리 초기화 시에 리스트 형식으로 각 노드를 구성해 Lazy 값을 저장할 수 있게 한다.
- 업데이트, 쿼리 시에 함수 형식이 조금 바뀐다.
Lazy Propagation 구현 // 트리 초기화
저는 Top → Down 방식으로 세그먼트 트리를 초기화합니다. 재귀 형식으로 초기화하게 되는데, 이 때 각 노드는 길이가 2인 리스트로 선언이 됩니다. 여기서 0번 인덱스는 쿼리에 필요한 값이 저장되고, 1번 인덱스에는 Lazy를 저장합니다. 이를 고려한다면, 초기화 자체는 기본 세그먼트 트리 초기화와 유사합니다.
def init(tree, node, left, right):
#my_list : 값이 저장되어 있는 배열
if left == right:
tree[node][0] = my_list[left]
return tree[node][0]
else:
mid = (left + right) // 2
tree[node][0] = init(tree, node * 2, left, mid) + init(tree, node * 2 + 1, mid + 1, right)
return tree[node][0]
Lazy Propagation 구현 // 연속 구간 업데이트
Lazy Propagation의 핵심인 연속 구간 업데이트입니다. 크게 달라진 것은 함수가 실행되었을 때, 현재 노드에 Lazy값이 있는지 확인하고 처리를 해주는 것입니다. 이 때, 노드의 성격에 따라 처리해주는 방식이 살짝 달라지게 됩니다.
현재 잎새노드라면 Lazy 값을 현재 노드에 반영해주고 Lazy 값을 0으로 초기화 해주면 됩니다. 잎새 노드가 아닐라면, 1. Lazy 값을 자식들에게 전달해주고, 2. 현재 노드에 Lazy 값을 반영해주고, 3. 그 다음 함수를 진행하면 됩니다. 저는 이런 전파가 계속 반복되기 때문에 Propagation 함수를 따로 하나 선언했습니다.
def propagation(tree, node, left, right):
if left != right:
tree[node * 2][1] += tree[node][1]
tree[node * 2 + 1][1] += tree[node][1]
# 현재 노드에 업데이트 해주고
tree[node][0] += tree[node][1] * (right - left + 1)
# 현재 lazy를 없애준다.
tree[node][1] = 0
return
def modify(tree, node, left, right, start, end, value):
if left == right and left == start:
if tree[node][1] != 0:
tree[node][0] += tree[node][1]
tree[node][1] = 0
tree[node][0] += value
return tree[node][0]
else:
if tree[node][1] != 0:
propagation(tree, node, left, right)
if start <= left and right <= end:
tree[node][0] += (right - left + 1) * value
if left != right :
tree[node * 2][1] += value
tree[node * 2 + 1][1] += value
return tree[node][0]
elif right < start or end < left:
return tree[node][0]
else:
mid = (left + right) // 2
a = modify(tree, node * 2, left, mid, start, end, value)
b = modify(tree, node * 2 + 1, mid + 1, right, start, end, value)
tree[node][0] = a + b
return tree[node][0]큰 틀은 위와 같습니다. 좀 더 자세히 구간을 나누면 다음과 같습니다.
- 현재 노드가 잎새 노드일 때
- 현재 노드의 구간보다 쿼리 구간이 클 때
- 현재 노드의 구간과 쿼리 구간이 겹치지 않을 때
- 1~3을 제외한 나머지 구간일 때
구간 별로 좀 더 상세히 살펴보겠습니다.
현재 노드가 잎새 노드일 때
이 경우는, 현재 노드에 Lazy가 있는지를 확인합니다. Lazy가 있다면, 업데이트를 해줍니다. 이 때, 잎새노드를 확인하는 방법은 left == right == start 인지로 확인해야합니다. 연속 구간이기 때문에 원하지 않는 구간의 잎새 노드가 나올 수 있기 때문입니다.
그리고 업데이트 해야하는 Value 값을 업데이트해주면 됩니다.
if left == right and left == start:
if tree[node][1] != 0:
tree[node][0] += tree[node][1]
tree[node][1] = 0
tree[node][0] += value
return tree[node][0]현재 쿼리 구간에 현재 노드의 구간이 포함될 때
현재 노드에 Lazy가 있는지를 확인합니다. Lazy가 있다면 현재 노드에 업데이트 한 후 Propagation을 합니다.
이 노드 아래로는 더 살펴볼 필요가 없습니다. 그렇기 때문에 이 구간에 변경된 Value를 업데이트 해주고, 자식들에게 Lazy를 전파해주면 됩니다. 전파 시에 조심해야할 부분은 현재 노드가 잎새 노드인지를 확인하고 전파해야한다는 것입니다. 앞에서 걸러낸 잎새 노드는 구간 내의 잎새 노드이기 때문에 현재 노드도 잎새 노드일 수 있습니다. 만약 현재 노드가 잎새 노드인 상태에서 자식에게 Lazy를 전파하게 되면 Index Error가 발생합니다.
if tree[node][1] != 0:
propagation(tree, node, left, right)
if start <= left and right <= end:
tree[node][0] += (right - left + 1) * value
if left != right :
tree[node * 2][1] += value
tree[node * 2 + 1][1] += value
return tree[node][0]
elif right < start or end < left:
return tree[node][0]현재 노드의 구간과 쿼리 구간이 겹치지 않을 때
이 구간 자체는 살펴볼 필요가 없습니다만, 이 노드에 Lazy가 있다면 조금 더 들여다봐야 합니다. 이 노드의 부모노드가 구간 Query에 연결되어있다면, 이 노드의 값도 필요한 쿼리와 연결이 되어있기 때문입니다. 이 노드에서 해야할 유일할 일은 현재 노드에 Lazy가 있는지 확인하고, 있다면 Propagation을 하는 것입니다. 이 경우, 재귀가 회수되는 과정에서 자동으로 부모 노드에 대해 필요한 값을 업데이트 하게 됩니다.
그 외의 경우
먼저 Lazy가 있다면 Propagation을 합니다. 그 후, 자식 노드들에 대해 다시 한번 재귀 탐색을 실행합니다. 그리고 필요한 부분까지 진행된 후 반환된 값을 현재 노드에 업데이트 해줍니다.
연속 구간 쿼리관련 간단 예시
먼저 아래 세그먼트 트리가 있다고 가정합시다. 가장 왼쪽은 구간을 나타내고, : 뒤에 있는 값은 구간의 합, / 뒤에 있는 값은 각 노드에 저장된 Lazy 값입니다.
이 때, 0~5 구간에 각각 4를 더하는 Query를 진행한다고 가정합니다.
먼저 왼쪽 자식노드를 탐색했습니다. 탐색 결과, 그 노드의 구간이 Quey 구간에 포함되는 것을 알게 되었습니다. 이 때, 현재 구간에 가지고 내려온 Value 4를 구간 크기만큼 곱해서 더해주고, 자식들에게 Lazy를 전파하고 Return 합니다. 그러면 아래 그림처럼 됩니다.
이제 루트 노드의 우측 노드를 탐색합니다. 현재 노드 Lazy가 없는 것이 확인되었으며, 구간 내에서 답을 확정지을 수 없기 때문에 자식 노드로 또 탐색을 합니다.
자식 노드로 한번 더 내려왔습니다. 이번 노드는 탐색하고자 하는 구간의 전체를 포함하고 있습니다. 따라서, 현재 노드에 Value 값을 업데이트 해주고 자식들에게 Lazy를 전파합니다.
전파가 완료되면 아래 그림처럼 바뀌게 됩니다. 현재 노드에서 할 일은 없기 때문에 Return 해주면 됩니다.
우측 노드를 탐험합니다. 구간에 포함되지 않는 노드이기 때문에 더 이상 볼 것이 없습니다. 따라서 Return 합니다.
4~7 구간 노드로 돌아와서 자식 노드들의 값을 더해줍니다. 그리고 Return 합니다.
루트 노드에 돌아온 후, 각 자식 노드들의 값을 더해줍니다. 쿼리가 완료되었습니다. 쿼리가 완료 시, 변경이 있는 부분은 아래 그림에서 빨간색으로 표시되어있습니다.
이 상태에서 다시 한번 업데이트 쿼리를 진행한다고 가정합니다. 이번 쿼리는 3~4에 -10을 하는 것입니다. 먼저 루트 노트의 왼쪽 자식부터 탐험합니다. 구간 내에 있는 노드지만, 좀 더 탐험해 볼 필요가 있습니다.
0~1 노드를 방문했습니다. 이 구간은 구간에서 벗어나는 노드이기 때문에 추가 탐험은 필요없습니다. 하지만, Lazy가 있는 것이 확인되었습니다. 이 노드의 값이 위의 노드에 유의미한 영향을 주기 때문에, Lazy가 있는 이 노드는 업데이트가 필요합니다.
Lazy를 업데이트하고 Propagation하면 아래 그림으로 바뀌게 됩니다.
돌아와서 우측 자식 노드를 탐험합니다. 이 구간에는 Lazy가 있으므로 Lazy를 업데이트하고, Propagation을 합니다.
Lazy를 전파하면 아래 그림과 같이 바뀌게 됩니다. 자식 노드가 있으니 다시 한번 왼쪽 자식노드부터 방문해줍니다.
왼쪽 자식 노드는 구간에 포함되지 않습니다. 그렇지만 Lazy가 있고, 이 노드의 값이 쿼리 구간에 포함된 부모 노드에 유의미한 영향을 주기 때문에 현재 노드를 업데이트 합니다. 단, 잎새 노드기 때문에 Propagation은 없습니다.
오른쪽 자식 노드를 탐험합니다. Lazy가 있으니 업데이트를 해줍니다. 잎새 노드이기 때문에 Propagation은 없습니다. 그리고 이 노드의 구간이 쿼리 구간에 포함됩니다. 현재 노드에 Value를 업데이트 해줍니다. 잎새 노드이기 때문에 자식 노드로의 Lazy Propagation은 없습니다.
이제 노란색으로 탐험했던 부분을 돌아가면서 각 자식 노드들의 합을 다시 한번 각 부모 노드들에 업데이트를 해주는 과정을 거칩니다. 아래 그림처럼 각 노드의 값과 Lazy가 변경되게 됩니다.
유사한 과정을 거쳐 4번 구간만 가지는 노드까지 탐색을 합니다. Lazy가 있으니 현재 노드에 업데이트 합니다. 그리고 자식 노드는 없기 때문에 Propagation은 하지 않습니다. 현재 구간이 쿼리 구간에 포함되기 때문에 Value 값을 현재 노드에 반영해줍니다. 마찬가지로 자식 노드가 없기 때문에 Propagation은 하지 않습니다.
쿼리를 완료하고 루트 노드로 돌아가면서, 각 부모 노드의 값을 업데이트 해줍니다. 쿼리가 완료되었을 때는 아래 그림처럼 바뀌게 됩니다.
Query 함수
쿼리에 대한 해답을 가져오는 함수도 필요합니다. 이 함수는 Update 함수만 제대로 이해하셨다면, 크게 어려움이 없습니다. 쿼리를 할 때, Lazy가 있을 수 있기 때문에 Lazy를 고려해주면 되고 방식은 Update 함수를 구성하는 것과 동일합니다. 다른 부분은 딱 두 가지 입니다.
- 포함되지 않는 구간을 탐색했을 때, Lazy가 있더라도 0을 Return 한다.
- 기본적인 Return 값은 탐색 결과의 값을 더 해서 Return 한다.
Update 함수와 Query 함수가 1번이 다른 이유는 구간에 포함되지 않는 값은 고려를 할 필요가 없기 때문입니다. 단, 쿼리를 처리하고 돌아가는 과정에서 각 부모 노드를 업데이트하는 것은 동일하게 합니다. 코드는 아래와 같습니다.
def query(tree, node, left, right, start, end):
# 잎새 노드일 때
if left == right and left == start:
if tree[node][1] != 0:
tree[node][0] += tree[node][1]
tree[node][1] = 0
return tree[node][0]
# 구간에 딱 들어올 때
else:
if tree[node][1] != 0:
propagation(tree, node, left, right)
if start <= left and right <= end:
return tree[node][0]
# 구간에 포함되지 않을 때
elif right < start or end < left:
return 0
# 애매하게 구간에 포함되었을 때
else:
mid = (left + right) // 2
a = query(tree, node * 2, left, mid, start, end)
b = query(tree, node * 2 + 1, mid + 1, right, start, end)
tree[node][0] = tree[node * 2][0] + tree[node * 2 + 1][0]
return a + b
'CS > 자료구조' 카테고리의 다른 글
| 정렬 알고리즘 정리 (0) | 2021.10.03 |
|---|---|
| Heap 구조 및 파이썬 구현 (0) | 2021.09.30 |
| 테이블과 해시 함수 (0) | 2021.09.26 |
| Trie(트라이) 자료구조 파이썬 (0) | 2021.09.21 |
| 파이썬, 세그먼트 트리 구현 (0) | 2021.09.21 |