트리 (3) - 느리게 갱신되는 세그먼트 트리(lazy propagation)

세그먼트 트리는 구간 쿼리에 특화되어 있어, 주어진 $[L, R]$ 구간의 합이나 최댓값/최솟값을 구하는 문제를 $O(\log N)$만에 잘 처리해 준다. 문제는 업데이트가 점 단위가 아닌 구간으로 주어지는 경우에 발생한다. 한 번의 점 단위 업데이트를 진행할 때 $O(\log N)$이 소요되므로, 일일이 구간 내 모든 값을 업데이트하는 것은 비효율적이다. 느리게 갱신되는 세그먼트 트리는 구간에 대한 정보를 담고 있는 세그먼트 트리의 구조를 십분 활용하여 구간 단위 업데이트를 $O(\log N)$만에 수행한다.

 

 

lazy propagation의 원리

기본 세그먼트 트리의 아이디어는 구간 쿼리를 처리할 때 구간 내에 포함되는 노드 밑으로는 더 이상 내려가지 않고 바로 결과를 반환하는 것이었다. 마찬가지로 lazy propagation의 핵심 아이디어는 구간 업데이트 요청이 들어왔을 때, 구간 내에 포함되는 노드는 해당 노드까지만 업데이트하고 나머지는 이후 필요할 때 업데이트하는 것이다.

 

이를 위해 lazy 배열을 만들어, 각 노드별로 아직 업데이트하지 않은 값인 lazy값을 관리해 준다. lazy값을 저장해 놓고, 필요할 때마다 lazy값을 원본 트리에 반영하는 push 함수를 구현하면 된다. push함수의 역할은 다음과 같다.

• lazy[node]를 tree[node]에 반영
• 자식 노드에 lazy[node]를 전파
• push가 끝난 lazy[node]의 값을 초기화

 

이때 원본 tree에 lazy값을 반영하는 방식과, 자식 노드에 lazy값을 전파하는 방식은 처리하려는 쿼리에 따라 조금씩 다를 수 있다. 만약 구간 합을 관리하는 트리에, 구간 내에 동일한 값을 더하는 업데이트 요청이 들어온 경우라면 lazy값에 구간의 길이를 곱하여 더함으로써 구간 합을 tree[node]에 반영해줄 수 있다. 코드는 아래와 같다.

def _push(self, node, s, e):
    if self.lazy[node]==0: return
    self.tree[node] += self.lazy[node]*(e-s+1)
    if not s==e:
        self.lazy[node*2] += self.lazy[node]
        self.lazy[node*2+1] += self.lazy[node]
    self.lazy[node] = 0

 

 

tree[node]값을 사용하기 전에는 항상 먼저 push를 해 주어야 한다. push를 해 주어 갱신된 값을 사용해야 트리가 망가지지 않기 때문이다. 따라서 update와 query 함수의 첫 부분에서 push를 해 준다. 또한 구간 내에 노드가 포함되어 lazy값을 설정해 줄 때에도, 결국 tree[node]를 반환해 주어야 하기 때문에 한번은 push를 하고 반환할 필요가 있다.

def update(self, node, s, e, l, r, val):
    self._push(node, s, e)
    if r<s or e<l: return self.tree[node]
    if l<=s and e<=r:
        self.lazy[node] += val
        self._push(node, s, e)
        return self.tree[node]
    m = (s+e)//2
    self.tree[node] = self.update(node*2, s, m, l, r, val)+self.update(node*2+1, m+1, e, l, r, val)
    return self.tree[node]
    
def query(self, node, s, e, l, r):
    self._push(node, s, e)
    if r < s or e < l: return 0
    if l <= s and e <= r: return self.tree[node]
    m = (s+e)//2
    return self.query(node*2, s, m, l, r)+self.query(node*2+1, m+1, e, l, r)

 

 

push함수 자체는 $O(1)$에 동작하므로, 모든 깊이에서 push가 일어나더라도 트리의 총 높이인 $O(\log N)$만에 구간 업데이트 처리가 가능하다.