백준 : 구간 합 구하기 (2042 , java)

오랜만에 백준들어와보니 예전에 풀었던 문제중에 재 채점되었고 틀렸다는 메시지를 받았습니다.

 

 

그래서 다시 풀어보기로 하고 다시풀었습니다...

 

구간 합 구하기 성공분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

256 MB

42958

7912

4110

24.211%

문제

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b(1 ≤ b ≤ N)번째 수를 c로 바꾸고 a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.

입력으로 주어지는 모든 수는 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

출력

첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

 

---

문제의 아이디어

 

단순하게 생각한다면 for문을 돌려서 매번 쿼리마다 for(i=a ; i<=b;i++) 하는 함수를 구하여 풀면됩니다.

하지만 이러한 경우 M번의 쿼리시 O(N *M) 이라는 시간이 걸리게 되고 N과 M의 최대값을 고려해볼때 

최악의경우 O(10000000 * 10000) 의 시간이 걸리게 됩니다.

 

우리에게는 O(logN * M)으로 시간을 줄이는 방법이 필요합니다.

 

이러한 경우 N개의 배열을 절반으로 쪼개었을 때 각각의 구간합을 알고 있고 또 그절반을 쪼갯을때 각각의 구간합을 알 수 있는 방법이 있다면 우리는 O(logN)이라는 시간으로 구간의 합을 구할 수 있습니다.

 

하지만 이러한 자료구조를 만드는 시간은 O(N*2) 이 걸리지만 M이 자주 호출되는 문제에서는 미리 구간의 합을 구해두고 빠르게 자료를 구할 수있는 것이죠!!. 물론 (처음부터 모든 경우의 구간합을 구한다면 빠르겟지만 경우의수가 너무많습니다.)

 

여기서 나오는 자료구조가 세그먼트 트리입니다.

 

redbinalgorithm.tistory.com/100

세그먼트 트리

 

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

public class boj {
	static int N, M, K;
	static long arr[];
	static long node[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		arr = new long[N + 1];
		node = new long[N * 4];

		for (int n = 1; n <= N; n++) {
			arr[n] = Integer.parseInt(br.readLine());
		}
		Init(1, N, 1);
		for (int m = 0; m < M + K; m++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if (a == 1) {
				long c = Long.parseLong(st.nextToken());
				long dif = c - arr[b];
				arr[b] = c;
				change(1,N,b,dif,1);
			} else {
				int c = Integer.parseInt(st.nextToken());
				System.out.println(sum(1,N,b,c,1));
			}

		}

	}

	public static long Init(int start, int end, int n) {

		if (start == end) {
			return node[n] = arr[start];
		}

		int mid = (start + end) / 2;

		return node[n] = Init(start, mid, n * 2) + Init(mid + 1, end, n * 2 + 1);
	}

	public static long sum(int start, int end, int i, int j, int n) {
		if (j < start || end < i)
			return 0;

		if (i <= start && j >= end)
			return node[n];

		int mid = (start + end) / 2;
		return sum(start, mid, i, j, n * 2) + sum(mid + 1, end, i, j, n * 2 + 1);
	}

	public static void change(int start, int end, int b, long dif, int n) {
		// b번째 수를 c로 바꾼다

		if (start > b || end < b)
			return;
		
		if(b==start&&b==end) {
			node[n]+=dif;
			return;
		}
		
		
		if (b >= start && b <= end) {
			int mid = (start + end) / 2;
			
			change(start, mid, b, dif, n * 2);
			change(mid + 1, end, b, dif, n * 2 + 1);
			
			node[n] += dif;
			return;
		}

	}
}

 

재채점이 뜬이유는 c의 경우 제약상황이 Integer 범위인줄 알았는데 문제에는 명시되어 있지 않으므로 long type이 들어올 수 있어서 스택오버플로우를 발생시켰습니다. 문제를 읽을 때 이러한 상황도 고려해주면 좋을것 같습니다.