🌲 Segment Tree 2 - 더 빠른 update를 위한 Lazy Propagation!

원본은 링크를 통해 확인하실 수 있습니다.

 

Intro 🚀

이전 글 마지막에 말씀드렸듯이 segment tree에서 특정 구간을 update할 때 leaf node를 일일이 방문해서 update하면 중복해서 방문하는 노드가 생깁니다. 이 때문에 정말 많은 update 연산을 해야 하는 경우 시간이 오래 걸릴 수 있습니다.

 

그래서 오늘은 더 빠른 udpate를 위한 기법인 Lazy propagation😴 에 대해 배워 보겠습니다!

 

Lazy Propagation 😴

지금부터 여러분이 노드를 직접 update하는 일꾼👷‍♀️👷이라고 생각해봅시다!

여러분은 아래 예제와 같은 segment tree를 돌아다니면서 노드를 udpate합니다.

 

 

만약 arr의 0번째부터 2번째 인덱스까지 update하라는 작업이 들어오면 여러분은 각각의 값을 저장하고 있는 leaf node (위 예제에서는 8, 9, 5번째 노드)를 방문한 후 값을 수정하고 그에 따라 조상 노드들의 값도 수정해야 합니다.

 

그런데 만약 여러분이 열심히 시간 들여가면서 하나하나 update한 노드를 한번도 사용하지 않으면 어떨까요? 아마 당신은 허탈하고 배신당한 기분이 들지도 모릅니다.

 

뿐만 아니라 당신은 이렇게 말할지도 모릅니다. '이제부터 삐뚤어 질테야! 😤 앞으로는 update하는 거 다 미룰꺼야! 정말 필요할 때만 update하고 그렇지 않으면 update 안 할꺼다 흥!😤'

 

바로 이 생각으로부터 Lazy propagation😴이 시작됩니다!

여기서 '정말 필요할 때만 update하고 그렇지 않으면 udpate 안 할 것이다'라는 말이 조금 추상적입니다.

정확히 말씀드리면 ✨Lazy propagation은 후손 노드를 접근해야 할 때까지 후손 노드를 update하는 것을 미룹니다.✨

 

또한 Lazy propagation을 구현할 때는 보통 segment tree를 나타내는 배열 $tree[]$와 크기가 같은 배열 $lazy[]$ 를 이용해 lazy node를 표현합니다. 즉 $lazy[i]$는 노드 $tree[i]$를 접근해야 할 때 증가시켜야 할 값 (문제에 따라 다를 수 있습니다) 입니다.

 

그렇다면 만약 $lazy[i]$가 0이라는 것은 무슨 뜻 일까요? 여러분이 생각하시는 대로 노드 $tree[i]$는 무언가 해야 할 update가 없다는 의미입니다. 🙅‍♂️

 

그럼 지금부터 Lazy propagation을 이용한 update와 query에 대해 알아보겠습니다!

 

Update

update 하는 과정은 다음과 같은 3단계로 나뉩니다.

 

1. Laziness를 없애서 현재 노드 원래 값으로 만들기. 그리고 나서 자식 노드에 lazy 표시하기.

2. 현재 노드가 update해야 할 구간에 포함되면 update하기

3. update할 적정 구간을 찾기 위해 자식 노드 방문

 

관련 코드는 다음과 같습니다.

 

Query

Query를 구하는 과정은 다음과 같은 2단계로 나뉩니다.

1. Laziness를 없애서 현재 노드 원래 값으로 만들기. 그리고 나서 자식 노드에 lazy 표시하기.

2. Query에서 요구한 적정 구간 찾기 위해 자식 노드 방문

관련 코드는 다음과 같습니다.

 

Let's do PS 😸

Lazy propagation에 대해 잘 이해되셨나요?

그렇다면 함께 BOJ 10999번 구간 합 구하기2 를 풀어봅시다!

 

도움이 필요하시면 아래 코드를 참고해주세요 😺

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ_10999 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] inputs = br.readLine().split(" ");
		
		int N = Integer.parseInt(inputs[0]);
		int M = Integer.parseInt(inputs[1]);
		int K = Integer.parseInt(inputs[2]);
		
		long[] arr = new long[N];
		long[] sgmt = new long[4 * N];
		long[] lazy = new long[4 * N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = Long.parseLong(br.readLine());
		}
		
		build(arr, sgmt, 0, N - 1, 1);
		
		for(int i = 0; i < M + K; i++) {
			inputs = br.readLine().split(" ");
			int a = Integer.parseInt(inputs[0]);
			int b = Integer.parseInt(inputs[1]);
			int c = Integer.parseInt(inputs[2]);
			long d = (inputs.length > 3) ? Integer.parseInt(inputs[3]) : 0;
			
			switch(a) {
				case 1 :
					update(sgmt, lazy, 0, N - 1, 1, b-1, c-1, d);
					break;
				case 2 :
					System.out.println(query(sgmt, lazy, 0, N - 1, 1, b-1, c-1));
					break;
			}
		}
		
	}
	
	public static void build(long[] arr, long[] sgmt, int lo, int hi, int idx) {
		if(lo == hi) {
			sgmt[idx] = arr[lo];
			return;
		}
		
		int mid = lo + (hi - lo) / 2;
		build(arr, sgmt, lo, mid, 2 * idx);
		build(arr, sgmt, mid + 1, hi, 2 * idx + 1);
		
		sgmt[idx] = sgmt[2 * idx] + sgmt[2 * idx + 1];
	}
	
	public static void update(long[] sgmt, long[] lazy, int lo, int hi, int idx, int i, int j, long val) {
		if(lazy[idx] != 0) {
			sgmt[idx] += (hi - lo + 1) * lazy[idx];
			
			if(lo != hi) {
				lazy[2 * idx] += lazy[idx];
				lazy[2 * idx + 1] += lazy[idx];
			}
			
			lazy[idx] = 0;
		}
		
		if(hi < i || j < lo) return;
		
		if(i <= lo && hi <= j) {
			sgmt[idx] += (hi - lo + 1) * val;
			
			if(lo != hi) {
				lazy[2 * idx] += val;
				lazy[2 * idx + 1] += val;
			}
			
			return;
		}
		
		int mid = lo + (hi - lo) / 2;
		update(sgmt, lazy, lo, mid, 2 * idx, i, j, val);
		update(sgmt, lazy, mid + 1, hi, 2 * idx + 1, i, j, val);
		
		sgmt[idx] = sgmt[2 * idx] + sgmt[2 * idx + 1];
	}
	
	public static long query(long[] sgmt, long[] lazy, int lo, int hi, int idx, int i, int j) {
		if(hi < i || j < lo) return 0;
		
		if(lazy[idx] != 0) {
			sgmt[idx] += (hi - lo + 1) * lazy[idx];
			
			if(lo != hi) {
				lazy[2 * idx] += lazy[idx];
				lazy[2 * idx + 1] += lazy[idx];
			}
			
			lazy[idx] = 0;
		}
		
		if(i <= lo && hi <= j) return sgmt[idx];
		
		int mid = lo + (hi - lo) / 2;
		return query(sgmt, lazy, lo, mid, 2 * idx, i, j) + 
			   query(sgmt, lazy, mid + 1, hi, 2 * idx + 1, i, j);
	}

}

 

 

Segment tree부터 Lazy propagation까지 잘 이해 되셨길 바라며 글을 마치겠습니다!

다음 글에서 만나요~~~👋👋👋

 

참고

https://bowbowbow.tistory.com/4

https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/