[자바] 백준 2042 - 구간 합 구하기

세그먼트 트리 문제다. 세그먼트 트리는 한 번도 그 어디에서도 들어본 적도 없었는데, 아래 글 읽으니까 어느 정도 이해가 됐다.

 

 

www.crocus.co.kr/648

세그먼트 트리(Segment Tree)

# 세그먼트 트리

- 시간 복잡도 : O(logN)

- tree 배열과 array 배열은 다른 데이터다. array 배열은 1부터 N까지의 값이 들어가 있는 배열이라면, tree 배열은 구간합들이 들어가있는 배열이다. 트리의 노드를 각 배열에 대치시킨 것이라고 생각하면 된다. 

- 초기 tree배열을 만들어주는 init() 메소드, array 배열에서 특정 index의 값이 변경됐을 때 tree 배열에서 상위 노드들의 값을 바꿔주는 update() 메소드, array배열에서의 left번부터 right번까지의 합을 구하는 sum() 메소드

   → 이 3개의 메소드가 세그먼트 트리의 주요 로직이다.

- 3개 메소드를 보면 전부 다 node 파라미터가 들어가 있는데, 웬만하면 처음 호출할 때에는 1을 넣는다. 이 1은 tree에서의 1번 index이고, tree배열의 1번 index는 최상위 노드, 즉 모든 데이터의 합계값을 가지고 있는 곳이다. 

/* 2021.01.06(수)*/
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main2042_구간합구하기 {

	static long[] array;
	static long[] tree;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] str = br.readLine().trim().split(" ");
		int N = Integer.parseInt(str[0]);
		int M = Integer.parseInt(str[1]);
		int K = Integer.parseInt(str[2]);
		
		array = new long[N+1];
		tree = new long[4*N];
		
		//0. array 배열에 숫자값들 입력 받기
		for(int i=1;i<s;=N;i++) {
			array[i] = Long.parseLong(br.readLine().trim());
		}
		
		//1. 초기값 세팅 - init()
		init(array,1,N,1);
		
		long caseCode, y, total = 0;
		int x;
		for(int i=0;i<s;M+K;i++) {
			str = br.readLine().trim().split(" ");
			
			caseCode = Long.parseLong(str[0]);
			x		 = Integer.parseInt(str[1]);
			y		 = Long.parseLong(str[2]);
			
			//2. update()
			if(caseCode == 1) {
				//x : x번째 숫자를
				//y : y로 바꾼다
				long diff = y-array[x];
				array[x] = y;
				update(array,1,N,x,1,diff);
			
			//3. sum()
			}else if(caseCode == 2) {
				total = sum(1,N,1,x,(int)y);
				sb.append(total+"\n");
			}
		}
		
		System.out.println(sb.toString().trim());

	}
	
	private static long sum(int start, int end, int node, int left, int right) {
		
		//start~end가 배열 범위이고, left~right가 구간합 범위인데 
		//left가 end보다 크거나 right가 start보다 작으면 
		//아예 배열 범위 밖이라는 뜻이니까 합을 구할 것도 없다.
		if(left>end || right <s;start) return 0;
		
		//근데 구하고자 하는 구간이 주어진 구간보다 클 수가 있나...?
		//노드는 1번부터 시작하고, 1번에 모든 합이 담겨있다!
		if(left<s;=start && end<s;=right) return tree[node];
		
		//위 if문에 모두 해당안되는 경우
		//-start~end가 left~right보다 모두 큰 경우
		//-start~end에 left~right의 일부가 걸쳐져 있는 경우 
		int mid = (start+end) / 2;
		return sum(start,mid, node*2, left, right) +
				sum(mid+1,end, node*2+1, left, right);
		
	}

	private static void update(long[] array, int start, int end, int idx, int node, long diff) {
		if(start>idx || end<s;idx ) return;
		
		//일단 node 1번(모든 합이 다 담겨있는 노드)부터 시작해서 
		//차이분(upNumber)만큼 더해준다
		tree[node] += diff;
		
		if(start != end) {
			int mid = (start+end)/2;
			update(array, start, mid, idx, node*2, diff);
			update(array, mid+1, end, idx, node*2+1, diff);
		}
	}

	//start와 end는 array에서의 위치
	//node 파라미터는 tree배열의 node를 가리킨다 
	private static long init(long[] array, int start, int end, int node) {

		if(start==end) return tree[node] = array[start];

		int mid = (start+end)/2;
		return tree[node] = init(array,start,mid,node*2) + init(array, mid+1, end, node*2+1);
	}
}