백준 10999 Java

문제

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

알고리즘 설명

구간합 구하는 방법에는 여러 가지가 있는데
나 같은 경우에는 범위 update 를 하는 경우는 Segment Tree를,
특정 수의 변경만 일어날 경우에는 Fenwick Tree를 사용한다.

range update가 일어날 경우 range 구간 만큼
tree update를 한다면 Time Out이 발생하므로,
update를 미뤄뒀다가 나중에 하는 개념인 Lazy Propagation 을 사용해야한다.
https://bowbowbow.tistory.com/4

구간이 update 될때마다 모든 노드에 update가 아니라,
조상 노드의 lazy가 자식 노드에 필요한 상황에만 전파를 시키는 개념이다.

**구간이 update 될때
lazy 는 가지고 있던 lazy 값을 tree에 update,
그리고 자식 lazy 들에게 분배 후, 자기 자신은 0으로 처리.

tree는 자기 자신 node에 value 값을 update 한 후
자식 lazy 들에게 value 값 분배까지.

sum 을 구할때는 미뤄왔던 lazy update를 다 한 더해줘야 함.**

설명을 여러 번 봐도 이해하기가 쉽지 않은 정말 어려운 개념이다.
코드를 직접 따라하면서 디버깅을 하며 트리를 찍어보면 감이 온다.

구현 코드

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

public class Main {

	static int N;
	static int Q;
	
	static int cal;
	
	static int list [];
	static long tree [];
	static long lazy [];
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken()) + Integer.parseInt(st.nextToken());
		
		list = new int [N+1];
		
		for (int i = 1; i<=N; i++) {
			list[i] = Integer.parseInt(br.readLine());
		}
		
		int size  = 1;
		while (size<N*2) {
			size<<=1;
		}
		cal = size/2-1;
		
		tree = new long [size];
		lazy = new long [size];
		
		makeInit(1, cal+1, size-1);
		
		
		
		for (int i = 0; i<Q; i++) {
			
			st = new StringTokenizer(br.readLine());
			int g = Integer.parseInt(st.nextToken());
			if (g==1) {				
				int left  = Integer.parseInt(st.nextToken())+cal;
				int right = Integer.parseInt(st.nextToken())+cal;
				long value = Integer.parseInt(st.nextToken());	
				update(1, cal+1, size-1, left, right, value);			
			} else {
				int left  = Integer.parseInt(st.nextToken())+cal;
				int right = Integer.parseInt(st.nextToken())+cal;
				long answer = sum(1, cal+1, size-1, left, right);
				System.out.println(answer);
			}
			
			
		}
		
		
	}

	private static long sum(int node, int start, int end, int left, int right) {
		// TODO Auto-generated method stub
		lazy_update(node, start, end);
		
		if (left > end || right < start) return 0;
		if (left <= start && right >= end) return tree[node];
		
		int mid = (start+end)/2;
		return sum(node*2, start, mid, left, right) +sum(node*2+1, mid+1, end, left, right);

	}

	private static void print() {
		// TODO Auto-generated method stub
		for (int i = 1; i<=15; i++) {
		System.out.print(tree[i]+" ");
		}System.out.println();
		for (int i = 1; i<=15; i++) {
		System.out.print(lazy[i]+" ");
		}System.out.println();
		System.out.println("######################");
	}

	private static void update(int node, int start, int end, int left, int right, long value) {
		// TODO Auto-generated method stub
		
		lazy_update(node, start, end);
				
		if (left > end || right < start) return;
		
		if (left <= start && right >= end) {
			tree[node] += (end-start+1)*value;
			if (start != end) {
				lazy[node*2] += value;
				lazy[node*2+1] += value;
			}
			return;
		}
		
		int mid = (start+end)/2;
		update(node*2, start, mid, left, right, value);
		update(node*2+1, mid+1, end, left, right, value);
		
		tree[node] = tree[node*2]+tree[node*2+1];
		
	}

	private static void lazy_update(int node, int start, int end) {
		// TODO Auto-generated method stub
		if (lazy[node] != 0) {			
			tree[node] += (end-start+1)*lazy[node];
			if (start!=end) {
				lazy[node*2] += lazy[node];
				lazy[node*2+1] += lazy[node];
			}
			lazy[node] = 0;
		}
		
		
	}

	private static void makeInit(int node, int start, int end) {
		// TODO Auto-generated method stub
		if (start == end) {
			if (start - cal > N) {
				tree[node] = 0;
			} else {
				tree[node] = list[start-cal];
			}
			return;
		}
		int mid = (start+end)/2;
		makeInit(node*2, start, mid);
		makeInit(node*2+1, mid+1, end);
		
		tree[node] = tree[node*2]+tree[node*2+1];
	}

}