BOJ. 2042번. 구간합 구하기

 

    구간합 구하기 문제는 세그먼트 트리라는 자료구조를 사용해서 푸는 문제이다. 정해진 조건에 따라 구간합을 구하고 싶은 구간을 특정지어 주는데, 구간이 주어질때마다 계산을 하게되면 결국 완전탐색법으로 푸는것과 다를바가 없다. 그러면 최소 n^4의 복잡도가 나오게 되고 당연히 시간초과가 발생한다. 

세그먼트 트리를 활용하면 이 복잡도를 nlogn에까지 줄일수 가 있어 굉장히 유리하다. 세그먼트 트리에 대한 자세한 내용은 아래 블로그를 참고하면 좋다. https://blog.naver.com/ndb796/221282210534 

41. 세그먼트 트리(Segment Tree)

이번 문제에서는 주어진 숫자배열로 세그먼트 트리를

1. 초기화하고

	// 세그먼트 트리 초기화, 재귀방식으로 구간에 따른 구간합을 저장
	private static long initSegmentTree(int s, int e, int nodeNum) {
		if(s==e) {
			return segmentTree[nodeNum] = num[s];
		}
		int mid = (s+e)/2;
		return segmentTree[nodeNum] = initSegmentTree(s,mid,2*nodeNum) + initSegmentTree(mid+1,e,2*nodeNum+1);
	}

2. 변경하고

	// 세그먼트 트리 업데이트, 해당 인덱스의 범위를 포함하는 모든 노드의 값을 갱신
	private static void updateSegmentTree(int s, int e, int nodeNum, int idx, long change) {
		// 인덱스가 범위 밖에 있는 경우엔 통과
		if (idx < s || idx > e) {
			return;
		}

		// 인덱스가 범위 안에 있는 경우에는 계속 내려가면서 합 갱신
		segmentTree[nodeNum] += change;
		if (s == e) {
			return;
		}
		int mid = (s + e) / 2;
		updateSegmentTree(s, mid, 2*nodeNum , idx, change);
		updateSegmentTree(mid+1, e, 2*nodeNum + 1, idx, change);
	}

3. 구간합을 구하는 과정 이 필요하다.

	// 세그먼트 트리 구간합 계산
	private static long sumSegmentTree(int s, int e, int nodeNum, int left, int right) {
		// 합하려는 구간이 범위 밖에 있는 경우
		if (left > e || right < s) {
			return 0;
		}

		// 합하려는 구간이 범위 안에 있는 경우
		if (left <= s && e <= right) {
			return segmentTree[nodeNum];
		}
		int mid = (s + e) / 2;
		return sumSegmentTree(s, mid, 2*nodeNum, left, right) + 
				sumSegmentTree(mid+1, e, 2*nodeNum + 1, left, right);
	}

 그리고 이 세가지 과정은 전부 재귀적인 방식을 이용하고, 코드 역시 크게 다르지 않다.

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

2042번: 구간 합 구하기

package week_17;

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

// segment tree - https://blog.naver.com/ndb796/221282210534 (안경잡이 개발자 블로그)
public class Day7BOJ2042부분합구하기 {

	static int n,m,k;
	static long[] num;
	static long[] segmentTree;
	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();
		StringTokenizer st = null;
		
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken()); // 수의 개수
		m = Integer.parseInt(st.nextToken()); // 수 변경 횟수
		k = Integer.parseInt(st.nextToken()); // 구간합 횟수
		num = new long[n+1];
		
		for(int i=1; i<=n; i++) {
			num[i] = Long.parseLong(br.readLine());
		}
		
		// segmentTreeSize는 log2를 취한 값에 + 1만큼의 완전이진트리를 구성해야됨
		int segmentTreeSize = (int)Math.pow(2, (int) Math.ceil(Math.log(n)/Math.log(2))+1);
		segmentTree = new long[segmentTreeSize+1];
		initSegmentTree(1,n,1);
		
		//
		for(int i=0; i<m+k; i++) {
			st = new StringTokenizer(br.readLine());
			int cmd = Integer.parseInt(st.nextToken());
			if(cmd == 1) {
				int idx = Integer.parseInt(st.nextToken());
				long to = Long.parseLong(st.nextToken());
				updateSegmentTree(1, n, 1, idx, to-num[idx]);
				num[idx] = to;
			}else {
				int left = Integer.parseInt(st.nextToken());
				int right = Integer.parseInt(st.nextToken());
				long res = sumSegmentTree(1,n,1,left,right);
				sb.append(res + "\n");
			}
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}

	// 세그먼트 트리 구간합 계산
	private static long sumSegmentTree(int s, int e, int nodeNum, int left, int right) {
		// 합하려는 구간이 범위 밖에 있는 경우
		if (left > e || right < s) {
			return 0;
		}

		// 합하려는 구간이 범위 안에 있는 경우
		if (left <= s && e <= right) {
			return segmentTree[nodeNum];
		}
		int mid = (s + e) / 2;
		return sumSegmentTree(s, mid, 2*nodeNum, left, right) + 
				sumSegmentTree(mid+1, e, 2*nodeNum + 1, left, right);
	}

	// 세그먼트 트리 업데이트, 해당 인덱스의 범위를 포함하는 모든 노드의 값을 갱신
	private static void updateSegmentTree(int s, int e, int nodeNum, int idx, long change) {
		// 인덱스가 범위 밖에 있는 경우엔 통과
		if (idx < s || idx > e) {
			return;
		}

		// 인덱스가 범위 안에 있는 경우에는 계속 내려가면서 합 갱신
		segmentTree[nodeNum] += change;
		if (s == e) {
			return;
		}
		int mid = (s + e) / 2;
		updateSegmentTree(s, mid, 2*nodeNum , idx, change);
		updateSegmentTree(mid+1, e, 2*nodeNum + 1, idx, change);
	}

	// 세그먼트 트리 초기화, 재귀방식으로 구간에 따른 구간합을 저장
	private static long initSegmentTree(int s, int e, int nodeNum) {
		if(s==e) {
			return segmentTree[nodeNum] = num[s];
		}
		int mid = (s+e)/2;
		return segmentTree[nodeNum] = initSegmentTree(s,mid,2*nodeNum) + initSegmentTree(mid+1,e,2*nodeNum+1);
	}
		
}