[백준 2268번] 수들의 합 7

 

 

 

package javaSana.Day0917.segmentTree;

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

public class B_2268 {
	static int N, M;
	static long[] arr, tree;

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

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new long[N + 1];
		tree = new long[N * 4];

		Arrays.fill(arr, 0);

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			if (a == 0) { // sum

				System.out.println(sum(1, N, 1, Math.min(b, c), Math.max(b, c)));
			} else if (a == 1) { // modify
				long dif = c - arr[b];
				arr[b] = c;
				modify(1, N, 1, b, dif);

			}

		}
	}

	static long sum(int start, int end, int node, int left, int right) {
		if (right < start || end < left)
			return 0;

		if (left <= start && end <= right) {
			return tree[node];
		}

		int mid = (start + end) / 2;
		return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
	}

	static void modify(int start, int end, int node, int idx, long dif) {
		if (idx < start || end < idx)
			return;

		tree[node] += dif;

		if (start == end)
			return;

		int mid = (start + end) / 2;
		modify(start, mid, node * 2, idx, dif);
		modify(mid + 1, end, node * 2 + 1, idx, dif);

	}
}