[KOITP] 구간 합

출    처 : http://koitp.org/problem/SDS_PRO_3_5/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.2 초	512 MB	2250	340 (15%)	279

문제

길이 N의 수열이 주어진다. 이 수열의 초기값은 1, 2, 3, ..., N이다. 그런데 이 수열의 변경이 빈번히 일어나고, 그런 도중에 어떤 연속된 부분의 합을 구하려 한다.

만약 N이 5인 경우를 생각하자. 초기에는 1, 2, 3, 4, 5 가 된다. 이 상황에서 3번째 수를 9로 변경하고 4번째 수를 10으로 변경하면 1, 2, 9, 10, 5가 된다. 이 때, 2번째부터 5번째까지 합을 구하라고 한다면 26을 출력하면 되는 것이다. 또, 이 상태에서 1번째 수를 -5로 변경하고, 3번째 수를 5로 변경하면 -5, 2, 5, 10, 5가 된다. 그 다음, 1번째부터 3번째까지 합을 구하라고 한다면 2가 된다.

이러한 질의를 해결하는 프로그램을 작성하시오.

입력

첫 번째 줄에 정수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000)

두 번째 줄에 질이의 개수 Q가 주어진다. (1 ≤ Q ≤ 200,000)

세 번째 줄부터 Q개의 줄에 걸쳐 질의의 정보가 주어진다. 각 질의는 다음 형태로 이루어진다.

• 0 x y : x번째 수를 y로 변경한다. (1 ≤ x ≤ N, -100,000 ≤ y ≤ 100,000)
• 1 x y : x번째 수부터 y번째 수까지의 합을 구한다. (1 ≤ x ≤ y ≤ N)

출력

질의 중 1로 시작하는 질의에 대해, 구한 합을 한 줄에 하나씩 출력한다. 이 때, 답의 범위가 32-bit 정수형의 범위를 초과할 수 있음에 유의하여라.

힌트

입력 예제

5
7
1 2 4
0 3 9
0 4 10
1 2 5
0 1 -5
0 3 5
1 1 3

출력 예제

9
26
2

< Comment >

 이전 문제를 푸는데에 시간을 너무 많이 허비한 탓에 풀이를 듣고 풀었는데도, 구현하는데 꽤 걸렸습니다. 일단 Indexed Tree 구조를 이용하였고, 아마 그냥 풀었다면 매번 정렬하는 식으로 풀었을텐데, 확실히 해당방법을 이용하여 푸니 빠른 시간 내에 풀수 있었습니다.

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

public class SubSum {

	public static int N = 0;
	public static int Q = 0;
	public static int startIdx = 0;
	
	public static long subSum[] = null;
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		Q = Integer.parseInt(br.readLine());
		
		makeIndexedTree(N);

		StringTokenizer st = null;
		int isQ = 0;
		int num1 = 0;
		int num2 = 0;
		long subSum = 0;
		
		for (int i = 0 ; i < Q ; i++) {
			st = new StringTokenizer(br.readLine());
			
			isQ = Integer.parseInt(st.nextToken());
			num1 = Integer.parseInt(st.nextToken());
			num2 = Integer.parseInt(st.nextToken());
			
			if (isQ == 1) {
				// 구간합 구하기
				subSum = getSubSum(startIdx + num1 - 1, startIdx + num2 - 1);
				bw.write("" + subSum + "\n");
			} else {
				// 구간합 갱신하기
				updateSubSum(startIdx + num1 - 1, num2);
			}
		}
		
		bw.flush();
		bw.close();
	}
	
	public static void makeIndexedTree (int n) {
		
		int treeNum = 0;
		int width = 0;
		int depth = 0;
		
		while (true) {
			
			width =  (int)Math.pow(2, depth++);
			treeNum += width;
			
			if (width >= n) {
				break;
			}
		}
		
		subSum = new long[treeNum + 1];
		startIdx = (int) Math.pow(2, depth - 1);
		for (int i =  0 ; i < n ; i++) {
			subSum[startIdx + i] = i + 1; 
		}
		
		int parentNodeIdx = 0;
		for (int i = treeNum ; i > 0 ; i --) {
			
			if (i % 2 == 0) {
				parentNodeIdx = i / 2;
				subSum[parentNodeIdx] = subSum[i] + subSum[i+1];
			}
		}
	}
	
	public static void updateSubSum (int idx, long updNum) {
		
		subSum[idx] = updNum;
		int parentNodeIdx = idx / 2;
		
		if (parentNodeIdx == 0) {
			return;
		}
		
		long parentUpdNum = 0;
		if (idx % 2 == 0) {			
			parentUpdNum = subSum[idx] + subSum[idx + 1];
		} else {
			parentUpdNum = subSum[idx - 1] + subSum[idx];
		}
		
		updateSubSum(parentNodeIdx, parentUpdNum);
	}
	
	public static long getSubSum(int head, int tail) {
		
		if (tail - head == 1) {
			return subSum[head] + subSum[tail];
		} else if (tail == head) {
			return subSum[head];
		}
		
		int parentIdx = 0;
		boolean headIsEven = ( head % 2 == 0 ? true : false );
		boolean tailIsOdd = ( tail % 2 == 1 ? true : false );
		
		if (headIsEven && tailIsOdd) {
			return getSubSum(head / 2, tail / 2);
		} else if (!headIsEven && tailIsOdd) {
			return subSum[head] + getSubSum(head + 1, tail);
		} else if (headIsEven && !tailIsOdd) {
			return getSubSum(head, tail - 1) + subSum[tail];
		} else {
			return subSum[head] + getSubSum(head + 1, tail - 1) + subSum[tail];
		}
	}
}