알고리즘 스터디 - 3주차

'22. 2. 11. 알고리즘 스터디 내용 및 회고

주제

1. Segment Tree(lazy propagation)
2. 백준 10999번(lazy propagation을 이용한 문제)

Segment Tree(lazy propagation)

Segment Tree에서 구간 업데이트를 빠르게 하기 위해 적용한 lazy propagation에 대해 공부하였음.
컴퓨터구조에서 배운 캐시의 개념과 비슷하게 생각하였음.
참고 : https://bowbowbow.tistory.com/4

1. 문제점

구간에 대해 업데이트를 한꺼번에 실행할 때, 기존 segment tree를 이용할 경우 모든 node를 거쳐가며 업데이트를 해줘야한다. 이때 한 개의 업데이트는 ($log_2(n)$

2. 아이디어

구간에 대해 업데이트 시 모든 노드에 같은 수를 빼고, 더할 경우 해당 노드에 자식 노드의 갯수 * 바뀌는 값만큼 적용해주면 똑같다.
해당 아이디어에서 문제점은 해당 구간에서의 구간합은 적용이 되지만 자식노드에 적용이 안되는 것이다. 그렇다고 자식노드를 또 업데이트 할 경우, 기존 segment tree와 별반 차이가 없다.
따라서 lazy라는 별도의 배열을 사용하여, 얼마만큼 변화를 적용시키는 지를 적용한 후, 해당 노드가 필요할 경우 lazy만큼 노드에 적용시켜 값을 얻는다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int stoi(String s) {return Integer.parseInt(s);}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = stoi(br.readLine());
		int[] arr = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < arr.length; i++) {
			arr[i] = stoi(st.nextToken());
		}
		
		Tree tree = new Tree(n, arr);
		
		// update -> start = 0, end = n - 1, left ~ right = to change dif;
		tree.update(0, n - 1, 1, 2, 4, -1);
		
		// sum -> start = 0, end = n - 1, left ~ right = sum left ~ right;
		System.out.println(tree.sum(0, n - 1, 1, 4, 4));
	}
	
	public static class Tree {
		int[] arr, tree, lazy;
		
		public Tree(int n, int[] arr) {
			this.arr = new int[n];
			tree = new int[n * 4];
			lazy = new int[n * 4];
			
			for(int i = 0; i < arr.length; i++) {
				this.arr[i] = arr[i];
			}
			init(0, n - 1, 1);
		}
		
		public int init(int start, int end, int node) {
			if(start == end) return tree[node] = arr[start];
			
			int mid = (start + end) / 2;
			return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
		}
		
		public void propagate(int start, int end, int node) {
			if(lazy[node] != 0) {
				if(start != end) {
					lazy[node * 2] += lazy[node];
					lazy[node * 2 + 1] += lazy[node];
				}
				tree[node] += lazy[node] * (end - start + 1);
				lazy[node] = 0;
			}
		}
		
		public int sum(int start, int end, int node, int left, int right) {
			propagate(start, end, node);
			if(left > end || right < start) {
				return 0;
			}
			if(left <= start && end <= right) {
				return tree[node];
			}
			
			int mid = (start + end) / 2;
			return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
		}
		
		public void update(int start, int end, int node, int left, int right, int dif) {
			propagate(start, end, node);
			if(right < start || left > end) return;
			
			if(left <= start && end <= right) {
				lazy[node] = dif;
				propagate(start, end, node);
				return;
			}
			
			int mid = (start + end) / 2;
			
			update(start, mid, node * 2, left, right, dif);
			update(mid + 1, end, node * 2 + 1, left, right, dif);
			
			tree[node] = tree[node * 2] + tree[node * 2 + 1];
		}
		
		public void print() {
			for(int i = 0; i < tree.length; i++) {
				System.out.println(i + " : " + tree[i]);
			}
		}
	}

}

백준 10999번(lazy propagation을 이용한 문제) : https://www.acmicpc.net/problem/10999

기존 2042번 구간 합 구하기 문제에서 사용했던 segment tree를 이용할 경우 시간초과가 나는 문제임.
다중 노드에 같은 수를 더하거나 빼는 문제로 lazy propagation를 적용한 segment tree를 사용하여 문제를 풀어야 한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int stoi(String s) {return Integer.parseInt(s);}
	public static long stol(String s) {return Long.parseLong(s);}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = stoi(st.nextToken());
		int M = stoi(st.nextToken());
		int K = stoi(st.nextToken());
		
		long[] arr = new long[N];
		
		for(int i = 0; i < arr.length; i++) {
			arr[i] = stol(br.readLine());
		}
		
		Tree tree = new Tree(N, arr);
		
		for(int i = 0; i < M + K; i++) {
			st = new StringTokenizer(br.readLine());
			
			int a = stoi(st.nextToken());
			int b = stoi(st.nextToken()) - 1;
			int c = stoi(st.nextToken()) - 1;
			
			if(a == 1) {
				tree.update(0, N - 1, 1, b, c, stol(st.nextToken()));
			}
			else {
				System.out.println(tree.sum(0, N - 1, 1, b, c));
			}
		}
	}
	
	public static class Tree {
		long[] arr, tree, lazy;
		
		public Tree(int n, long[] arr) {
			this.arr = new long[n];
			tree = new long[n * 4];
			lazy = new long[n * 4];
			
			for(int i = 0; i < arr.length; i++) {
				this.arr[i] = arr[i];
			}
			init(0, n - 1, 1);
		}
		
		public long init(int start, int end, int node) {
			if(start == end) return tree[node] = arr[start];
			
			int mid = (start + end) / 2;
			return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
		}
		
		public void propagate(int start, int end, int node) {
			if(lazy[node] != 0) {
				if(start != end) {
					lazy[node * 2] += lazy[node];
					lazy[node * 2 + 1] += lazy[node];
				}
				tree[node] += lazy[node] * (end - start + 1);
				lazy[node] = 0;
			}
		}
		
		public long sum(int start, int end, int node, int left, int right) {
			propagate(start, end, node);
			if(left > end || right < start) {
				return 0;
			}
			if(left <= start && end <= right) {
				return tree[node];
			}
			
			int mid = (start + end) / 2;
			return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
		}
		
		public void update(int start, int end, int node, int left, int right, long dif) {
			propagate(start, end, node);
			if(right < start || left > end) return;
			
			if(left <= start && end <= right) {
				lazy[node] = dif;
				propagate(start, end, node);
				return;
			}
			
			int mid = (start + end) / 2;
			
			update(start, mid, node * 2, left, right, dif);
			update(mid + 1, end, node * 2 + 1, left, right, dif);
			
			tree[node] = tree[node * 2] + tree[node * 2 + 1];
		}
		
		public void print() {
			for(int i = 0; i < tree.length; i++) {
				System.out.println(i + " : " + tree[i]);
			}
		}
	}

}