[Algorithm] Lazy Propagation( 지연전파 ) ( + BOJ10999 ) With JAVA

https://lordofkangs.tistory.com/411

[Alogorithm] 세그먼트 트리( Segment Tree ) 구간합 구하기 ( + BOJ2042 ) With Python,JAVA

 
지난 포스팅에서 세그먼트 트리로 구간합을 O(logN) 시간복잡도로 구해보았다. 
 
수열의 변경이 자주 일어나지 않는다면 메모리를 적게 차지하는 배열이 좋지만 변경이 자주 일어난다면 처리속도가 빠른 세그먼트 트리를 구성하는 것이 좋다. (트레이드-오프) 그럼 이번 포스팅에서는 세그먼트 트리의 성능을 더 높혀보자!
 
지난 포스팅에서는 수열에서 수 한개만 변경되는 경우를 다루어보았다. 이때 시간복잡도는 O(logN)이다. 그런데 만약 변경된 수가 n개라면 시간복잡도는 O(NlogN)이 되어버린다. 늘어난 수만큼 탐색해야하는 범위도 늘어나기 때문이다.  지연전파(Lazy Propagation) 알고리즘은 변경되는 수가 증가해도 시간복잡도를 O(logN)으로 유지하도록 하는 알고리즘이다. 
 
 
 

출처( 이미지 클릭 )

 
 
예를들어,  3번째-7번째 수를 모두 2씩 증가한다고 가정해보자.  값을 변경하려고 세그먼트 트리의 리프노드까지 탐색하면 O(NlogN)의 시간복잡도가 걸린다. 그래서 리프노드까지 내려가기 전에, 3-7구간 안에 포함되는 구간의 노드라면 탐색을 멈추고 변경작업을 지연시킨다. 
 
위 트리에서는 3-4구간 노드와 5-7구간 노드가 3-7구간에 포함된다. 3-4구간 노드와 5-7구간 노드의 값만 변경하고 자식트리는 탐색하지 않고 변경을 지연(Lazy)시킨다. 그럼 자식트리는 변경이 지연되었음을 표시해야 한다. 그래서 세그먼트트리와 같은 형태의 자료구조를 하나 만든다. 그리고 같은 인덱스 위치에 변경값 2를 저장한다. 3-4구간을 가리키는 노드가 i라면 자식구간의 노드는 2*i와 2*i+1이다. lazy[2*i]와 lazy[2*i+1]에 변경값 2를 저장하는 원리이다. 
 
이렇게 지연시켜도 되는 이유는 당장은 변경이 필요없기 때문이다. 그러다가 세그먼트 트리를 update하거나 sum을 하려고 해당 노드를 방문하게 되면 그 때 변경값을 처리한다. 그리고 자식노드가 있다면 자식노드에게 지연을 전파(Propagation)한다. 이와 같이, O(NlogN)으로 한번에 처리하지 않고 지연시켰다가, O(logN) 작업 중에 해당 노드를 방문하게 되면, 그때 지연된 값을 처리하여 시간복잡도를 유지하는 방식이 지연전파(Lazy Propagation) 알고리즘이다. 
 
그럼 이를 코드로 확인해 보자.
 
 

◎코드
 

https://www.acmicpc.net/problem/10999

10999번: 구간 합 구하기 2

 
JAVA

import java.io.*;
import java.util.StringTokenizer;

//#BOJ10999 구간합 구하기2 ( prefixsum )
public class Main {

    static StringTokenizer st;
    static long[] arr; // 수열
    static long[] tree; // 세그먼트 트리
    static long[] lazy; // lazy 트리


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        arr = new long[n+1];
        tree = new long[4*n+1];
        lazy = new long[4*n+1];
        
        //수열 초기화
        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine());
            arr[i]=Long.parseLong(st.nextToken());
        }
        
        //세그먼트 트리 초기화
        init_tree(1,n,1);

        int z = m+k;
        while(z-- > 0){
            String[] str = br.readLine().split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);
            int c = Integer.parseInt(str[2]);
            
            // 세그먼트 트리 변경하기
            if(a==1){ 
                long diff = Long.parseLong(str[3]);
                update_tree(1,n,1,b,c,diff);
            }
            // 구간합 구하기
            else if(a==2){
                sb.append(sum_tree(1,n,1,b,c)).append("\n");
            }
        }
        
        //출력
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    // 세그먼트 트리 초기화
    public static long init_tree(int start, int end, int node){
        if( start == end ) tree[node] = arr[start];
        else {
            int mid = (start+end)/2;
            tree[node] = init_tree(start,mid,2*node) + init_tree(mid+1,end,2*node+1);
        }
        return tree[node];
    }

    // 구간 합 구하기
    public static long sum_tree(int start,int end,int node,int fs,int fe){
        propagation(start,end,node); // 방문한 노드에 지연값이 있다면 처리하기 
        if( fs > end || fe < start ) return 0;
        if( fs <= start && end <= fe ) return tree[node];

        int mid = (start+end)/2;
        return sum_tree(start,mid,2*node,fs,fe) + sum_tree(mid+1,end,2*node+1,fs,fe);
    }

    // 구간 변경 하기
    public static void update_tree(int start,int end, int node,int fs, int fe,long diff){
        propagation(start,end,node); // 방문한 노드에 지연값이 있다면 처리하기
        if(start > fe || end < fs ) return;
        if( fs <= start && end <= fe ) { // 방문한 노드가 변경구간 안에 있다면 변경작업 지연
            tree[node] += (end-start+1)*diff; // 리프노드의 개수만큼 변경값 더하기
            if( start != end ){
                lazy[2*node] += diff; // 자식노드 변경작업 지연됨을 표시하기
                lazy[2*node+1] += diff; // 자식노드 변경작업 지연됨을 표시하기
            }
            return; // 변경작업 중지
        }
        // 변경 구간 탐색하기
        int mid = (start+end)/2;
        update_tree(start,mid,2*node,fs,fe,diff);
        update_tree(mid+1,end,2*node+1,fs,fe,diff);
        tree[node] = tree[2*node] + tree[2*node+1]; // 상위 구간은 변경되었으니 변경된 구간합 초기화하기
    }

    // 자식노드에게 지연전파하기 
    public static void propagation(int start,int end,int node){
        if(lazy[node] != 0) { // 지연값이 있는 경우
            tree[node] += (end-start+1)*lazy[node]; // 지연된 변경값을 처리
            if(start != end){ // 자식에게 지연 전파
                lazy[2*node] += lazy[node];
                lazy[2*node+1] += lazy[node];
            }
            lazy[node] = 0; // 원복
        }
    }
}

 
 

---

 
 

참고자료

느리게 갱신되는 세그먼트 트리