구간 합 구하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);

		int N, M, K;
		long[] arr, tree;

		String[] line1 = br.readLine().split(" ");
		N = Integer.parseInt(line1[0]);
		M = Integer.parseInt(line1[1]);
		K = Integer.parseInt(line1[2]);

		arr = new long[N];

		for (int i = 0; i < N; i++) {
			arr[i] = Long.parseLong(br.readLine());
		}
		int height = (int)Math.ceil(getTreeHeight(N));
		tree = new long[1 << (height + 1)];

		init(arr, tree, 1, 0, N - 1);
		int a, b, c;
		for (int i = 0; i < M + K; i++) {
			String[] line2 = br.readLine().split(" ");
			a = Integer.parseInt(line2[0]);
			b = Integer.parseInt(line2[1]);
			c = Integer.parseInt(line2[2]);
			if (a == 2) {
				pw.println(sum(tree, 1, 0, arr.length - 1, b - 1, c - 1));
				pw.flush();
			} else {
				update(tree, 1, 0, arr.length - 1, b - 1, c);
			}
		}
	}

	public static double getTreeHeight(long num) {
		return Math.log10(num) / Math.log10(2);
	}

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

	public static long update(long[] tree, int node, int start, int end, int updated_index, long value) {
		if (!(start <= updated_index && updated_index <= end)) {
			return tree[node];
		}
		if (start == end) {
			return tree[node] = value;
		}
		int mid = (start + end) / 2;
		return tree[node] = update(tree, 2*node, start, mid, updated_index, value)
				+ update(tree, (2*node)+1, mid + 1, end, updated_index, value);
	}

	public static long sum(long[] tree, int node, int start, int end, 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(tree, 2*node, start, mid, left, right) + sum(tree, (2*node)+1, mid + 1, end, left, right);
	}
}