BOJ. Prefix sum (2042)

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] line = br.readLine().split(" ");
		int n = toi(line[0]), m = toi(line[1]), k = toi(line[2]);
		long[] arr = new long[n];
		long[] seg = new long[1 << ((long)Math.ceil(Math.log(arr.length) / Math.log(2)) + 1)];

		for(int i = 0; i < n; i++) arr[i] = tol(br.readLine());
		init(seg, arr, 0, n - 1, 1);
		for(int i = 0; i < m + k; i++) {
			line = br.readLine().split(" ");
			int b = toi(line[1]);
			long c = tol(line[2]);
			if(line[0].equals("1")) {
				update(seg, 0, n -1, 1, b - 1, c - arr[b - 1]);
				arr[b - 1] = c;
			}
			else sb.append(sum(seg, 0, n -1, b - 1, (int)c - 1, 1) + "\n");
		}
		print(sb);
	}

	static long init(long[] seg, long[] arr, int l, int r, int idx) {
		if(l == r) return seg[idx] = arr[l];
		int mid = (l + r) / 2;
		return seg[idx] = init(seg, arr, l , mid, 2 * idx) + init(seg, arr, mid + 1, r, 2 * idx + 1);
	}

	static boolean update(long[] seg, int l, int r, int idx, int targetIdx, long diff) {
		if(l > targetIdx || r < targetIdx) return false;;
		seg[idx] += diff;
		if(l == r) return true;
		int mid = (l + r) / 2;
		if(!update(seg, l, mid, 2 * idx, targetIdx, diff)) update(seg, mid + 1, r, 2 * idx + 1, targetIdx, diff);
		return true;
	}

	static long sum(long[] seg, int l, int r, int start, int end, int idx) {
		if(l > end || r < start) return 0;
		else if(start <= l && r <= end) return seg[idx];
		int mid = (l + r) / 2;
		return sum(seg, l, mid, start, end, 2 * idx) + sum(seg, mid + 1, r, start, end, 2 * idx + 1);
	}

	static int toi(String s) { return Integer.parseInt(s); }
	static long tol(String s) { return Long.parseLong(s); }
	static <T> void print(T s) { System.out.print(s); }
	static <T> void println(T s) { System.out.println(s); }
}