[java] 백준(BOJ) - 구간합구하기

문제

백준-구간합구하기
요청에 따라 원소를 교체하거나 구간의 합을 구하는 문제

풀이

세그먼트 트리 개념을 익힌 만큼 적용 겸 푸는 문제
완전 정석대로여서 초기 입력, 값 업데이트, 구간 구하기가 들어있다

다만 타입을 long으로 잡아줘야한다

소스코드

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

public class b2042_구간합구하기 {

	private static int K;
	private static int M;
	private static int N;
	static long[] arr;
	static long[] nums;

	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());

		StringBuilder sb = new StringBuilder();
		// 세그먼트 트리 크기
		long H = (long) (Math.ceil(Math.log(N) / Math.log(2)));
		long size = (long) Math.pow(2, H + 1);
		arr = new long[(int) size];
		nums = new long[N];
		for (int i = 0; i < N; i++) {
			nums[i] = Long.parseLong(br.readLine());
		}

		init(1, 0, N - 1);
		for (int i = 0; i < M + K; i++) {
			st = new StringTokenizer(br.readLine());
			if (st.nextToken().equals("1")) { // b를 c로 교체
				int b = Integer.parseInt(st.nextToken());
				long diff = nums[b - 1] * -1;
				long newVal = Long.parseLong(st.nextToken());
				diff = diff + newVal;
				update(1, 0, N - 1, b - 1, diff);
			} else { // b부터 c까지 합
				int b = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				sb.append(sum(1, 0, N - 1, b - 1, c - 1));
				sb.append("\n");
			}
		}
		System.out.println(sb.toString());
	}

	private static long init(int node, int start, int end) {
		if (start == end) {
			arr[node] = nums[start];
			return arr[node];
		}
		int mid = (start + end) / 2;
		return arr[node] = init(node * 2, start, mid) + init(node * 2 + 1, mid + 1, end);
	}

	private static long sum(int node, int start, int end, int left, int right) {
		if (end < left || right < start)
			return 0;
		if (left <= start && end <= right)
			return arr[node];
		int mid = (start + end) / 2;
		return sum(node * 2, start, mid, left, right) + sum(node * 2 + 1, mid + 1, end, left, right);
	}

	private static void update(int node, int start, int end, int idx, long diff) {
		if (start == end && idx == start)
			nums[idx] += diff;

		if (idx > end || idx < start)
			return;
		arr[node] += diff;
		if (start != end) {
			int mid = (start + end) / 2;
			update(node * 2, start, mid, idx, diff);
			update(node * 2 + 1, mid + 1, end, idx, diff);
		}
	}
}