[알고리즘] Segment Tree, lazy propagation

1. Segment Tree

세그먼트 트리는 트리 형태의 데이터를 활용해 어떤 구간에 대한 정보를 활용하는 데 사용한다.

아직 블로그 글에서 세그먼트 트리를 다루지 않았지만, 후에 다루어 볼 것이고, 먼저 lazy propagtion의 적용을 이 글에서 다루어 볼 것이다.

 

---

2. lazy propagation

느린 전파라고도 말하지만, 게으른 전파가 알고리즘을 더 잘 나타낼 수 있는 단어라고 생각하여 게으른 전파라 부르겠다.

세그먼트 트리에서 게으른 전파는 값을 갱신할 때 특정 값이 아니라 범위의 값을 변경할 때 사용한다. 세그먼트 트리는 log(N)으로 가능하지만, 범위의 값을 경신하기 위해 Nlog(N)의 연산이 필요하게 된다. 그래서 갱신을 트리의 모든 값에 항상 적용하는 게 아니라 필요할 때만 하는 것이다.

 

만약 세그먼트 트리에서 특정 범위에 값을 갱신한다면 다음과 같은 방식으로 모든 리프 노드까지 내려가서 적용해야 한다. 이 방법 대신 lazy값을 두어 지금 갱신하는 것이 아니라 나중에 사용할 때 갱신하는 방법을 선택한다.

갱신하려는 범위에 따라 색으로 표현사면 다음과 같다. 초록색은 범위를 일부 포함하는 경우, 파란색은 범위를 전부 포함하는 경우, 빨간색은 범위를 벗어난 경우를 의미한다.

초록색 범위는 더 탐색이 필요하기 때문에 더욱 깊이 탐색한다. 이 탐색은 아래의 코드에서도 확인할 수 있지만, 여느 세그먼트 트리 탐색과 같은 방식을 적용한다.

만약 파란색에 도달하면, 모든 범위가 속하게 된다. 그리고 여시거 lazy propagation의 핵심이 적용된다. 세그먼트 트리에서는 지금 탐색하는 범위에 따라 최종 속하게 되는 리프 노드의 개수를 알 수 있고, 파란색 점에서는 해당 리프 노드들을 모두 적용할 수 있도록 한다. 예를 들어 왼쪽의 파랑 점은 리프 노드이므로 2를 더하는 작업만 하여 5가 되고, 오른쪽 파랑 점은 아래의 2개의 리프 노드가 있으므로 4를 더하여 13이 된다. 추가적인 자식 노드가 있다면 자식 노드에는 2를 더하는 작업을 하는 것이 아니라 lazy 값에 2를 임시 저장하고, 필요할 때 사용한다.

빨간색 점은 범위를 벗어난 것이므로, 탐색을 종료한다.

 

---

3. 문제에서의 적용

간단한 lazy propagation 적용으로 해결할 수 있는 문제, 추가적인 활용이 필요한 두 문제를 살펴볼 것이다.

 

3.1. 구간 합 구하기 2

문제 링크 : https://www.acmicpc.net/problem/10999

10999번: 구간 합 구하기 2

문제 풀이 링크 :

- python : https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/10000/10900/10999.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

class SegmentTree:
    def __init__(self, N: int, seq: list[int]) -> None:
        self.N = N
        self.seq = [0] + seq
        self.tree = [0] * (1 << (ceil(log2(N)) + 1))
        self.lazy = [0] * (1 << (ceil(log2(N)) + 1))
        self.init_tree(1, 1, N)

    def mid(self, start: int, end: int) -> int:
        return (start + end) // 2

    def init_tree(self, node: int, start: int, end: int) -> None:
        if start >= end:
            self.tree[node] = self.seq[start]
            return
        mid = self.mid(start, end)
        self.init_tree(node * 2, start, mid)
        self.init_tree(node * 2 + 1, mid + 1, end)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def update_lazy(self, node: int, start: int, end: int) -> None:
        if self.lazy[node]:
            self.tree[node] += (end - start + 1) * self.lazy[node]
            if start != end:
                self.lazy[node * 2] += self.lazy[node]
                self.lazy[node * 2 + 1] += self.lazy[node]
            self.lazy[node] = 0

    def update_range(
        self, node: int, start: int, end: int, left: int, right: int, diff: int
    ) -> None:
        self.update_lazy(node, start, end)
        if right < start or end < left:
            return
        if left <= start and end <= right:
            self.tree[node] += (end - start + 1) * diff
            if start != end:
                self.lazy[node * 2] += diff
                self.lazy[node * 2 + 1] += diff
            return
        mid = self.mid(start, end)
        self.update_range(node * 2, start, mid, left, right, diff)
        self.update_range(node * 2 + 1, mid + 1, end, left, right, diff)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def query(self, node: int, start: int, end: int, left: int, right: int) -> int:
        self.update_lazy(node, start, end)
        if right < start or end < left:
            return 0
        if left <= start and end <= right:
            return self.tree[node]
        mid = self.mid(start, end)
        left_sum = self.query(node * 2, start, mid, left, right)
        right_sum = self.query(node * 2 + 1, mid + 1, end, left, right)
        return left_sum + right_sum

lazy propagation만을 적용하여 해결할 수 있는 문제이므로, 모드를 기반으로 설명하겠다. 전반적인 코드는 일반적인 세그먼트 트리와 같지만, lazy가 적용된다. 클래스 초기화에서 트리의 크기와 같은 lazy 배열을 생성한다. 그리고 query, update를 할 때 lazy를 적용하는 부분이 추가된다.

update_lazy() 메서드를 보면, lazy 값이 있다면 tree에 적용하고, 자식 중 리프 노드의 갯수만큼 lazy에 다시 적용한다.

update_range(), query()메서드에서는 항상 lazy를 먼저 적용하고 다른 작업을 수행한다.

 

3.2. XOR

문제 링크 : https://www.acmicpc.net/problem/12844

12844번: XOR

문제 풀이 링크 :

- python : https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/12000/12800/12844.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

전반적인 코드는 유사하게 적용된다. 하지만 XOR의 특성을 고려해서 lazy를 적용해야 한다. 활용할 XOR의 특징은 교환 법칙, 항등원, 역원이다.

1. 교환 법칙은 연산자를 적용하는 연산 순서가 바뀌어도 된다는 것이다. 예를 들어 1 + 2 = 2 + 1과 같다. XOR에도 적용되며, 1 ^ 2 = 2 ^ 1과 같다. ( ^연산은 일반적으로 제곱을 나타낼 때 활용하지만, 코드에서는 XOR연산으로 동작하기 때문에 이 글에서는 XOR 연산으로 사용하겠다.)

2. 항등원은 어떤 연산에 대하여 자기 자신이 나오는 값이다. 예를 들어 더하기 연산의 항등원은 0이고, 곱하기 연산의 항등원은 1이다. XOR연산에서는 항등원이 0이 된다.

3. 역원은 어떤 연산에 대하여 항등원이 나오게 하는 값이다. 예를 들어 x에 대하여 더하기 연산의 항등원은 -x이고, 곱하기 연산의 역원은 1/x이다. XOR연산에서 역원은 -x이다.

 

이 조건들을 활용하면 다음과 같은 계산 과정을 도출할 수 있다. 여러 구간에 걸쳐 x만큼 XOR을 한다고 하면,

(a^x) ^ (b^x) ^ (c^x)와 같은 형태가 되는데, 이 식을 조금 수정한다면, (a^b^c) ^ (x^x^x)와 같은 형태가 된다.

여기서 같은 수에 XOR연산을 적용할 때, 해당하는 숫자가 홀수개이면 그 결과는 x가 되고, 짝수개이면 0이 됨을 알 수 있다.

 

def update_lazy(self, node: int, start: int, end: int) -> None:
    if self.lazy[node]:
        if (end - start + 1) % 2:
            self.tree[node] ^= self.lazy[node]
        if start != end:
            self.lazy[node * 2] ^= self.lazy[node]
            self.lazy[node * 2 + 1] ^= self.lazy[node]
        self.lazy[node] = 0

그래서 다음과 같이 리프 노드 개수에 따라 XOR를 적용했다.

 

---

4. 생각 정리

세그먼트 트리는 여러 차례 풀어봤지만, 풀이 과정을 잘 정리해보지는 못한 것 같다. 이후에 조금 더 상세하게 정리하면 좋을 것 같다.

게으른 전파도 이번 기회에 문제를 풀어보게 되었지만, 조금 더 상세한 설명을 위해 글을 보강할 필요가 있을 것 같다.