[자바] 백준 2042번: 구간합 구하기(실패)

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

2042번: 구간 합 구하기

 

실패했다.

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

public class P2042 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		int idx = n;
		long[] num = new long[n + 1];
		long[] sum = new long[n + 1];

		for (int i = 1; i <= n; i++) {
			num[i] = Long.parseLong(br.readLine());
			sum[i] = sum[i - 1] + num[i];
		}

		for (int i = 0; i < m + k; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			long c = Long.parseLong(st.nextToken());

			if (a == 1) {
				// 숫자 변경하는 경우
				num[b] = c;
				idx = Math.min(idx, b - 1); // 0~b-1까지는 sum의 값이 맞고, b부터는 갱신이 필요함
			} else if (a == 2) {
				// 부분합 출력하는 경우
				if (c > idx) {
					// c앞쪽이 숫자가 바뀌어서 sum을 갱신해야함
					for (int j = idx + 1; j <= c; j++) {
						sum[j] = sum[j - 1] + num[j];
					}
					idx = (int) c;
				}
				System.out.println(sum[(int) c] - sum[b - 1]);
			}
		}
	}

}

숫자를 저장할 num배열,

누적합을 젖아할 sum배열을 만들었다.

 

idx라는 변수를 사용하는데,

sum배열에서 0~idx번째 숫자는 누적합이 맞게 되어있고, idx+1부터는 숫자가 바뀐 것이 있어 누적합을 갱신해야한다,

 

숫자를 바꾸는 경우

idx를 해당 숫자의 인덱스-1로 갱신하고,

 

부분합을 출력하는 경우

구간(a,b)가 idx보다 작은쪽에 있다면 sum배열에 누적합이 제대로 입력되어있는 상태이므로 바로 계산하여 출력(O(1))

구간(a,b)가 idx보다 큰쪽에 있다면 sum배열을 필요한 만큼 갱신하고 출력한다.

.

.

작동은 잘 된다고 생각했는데

10%에서 시간초과가 났다.

 

알고보니 세그먼트 트리 알고리즘이라는 것을 사용해야한다고 한다.

이것은 다음에 따로 공부해서 다시 풀어보겠다.