[백준-BOJ] 2042

www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

 

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

public class Main {
	public static void main(String[] args) throws IOException {
		Main m = new Main();
		m.doit();
	}


	int N;
	int K;
	int M;

	long [] arr = new long[1000002];
	long [] tree = new long[4000002];
	public void doit() throws IOException{
	//	System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String [] inputStr = br.readLine().split(" ");
		N = Integer.parseInt(inputStr[0]);
		M = Integer.parseInt(inputStr[1]);
		K = Integer.parseInt(inputStr[2]);
		
		for(int i = 0; i < N; i++){
			arr[i] = Long.parseLong(br.readLine());
		}
		init(1, 0, N-1);
		for(int i = 0; i < M + K; i++){
			inputStr = br.readLine().split(" ");
			if("1".equals(inputStr[0])){
				int t2 = Integer.parseInt(inputStr[1]);
				long t3 = Long.parseLong(inputStr[2]);
				t2 -= 1;
				long diff = t3 - arr[t2];
				arr[t2] = t3;
				update(1, 0, N-1, t2, diff);
			}else{
				int t2, t3;
				System.out.println(sum(1, 0, N-1, Integer.parseInt(inputStr[1])-1, Integer.parseInt(inputStr[2])-1));
			}
		}
//		printArr(arr, N);
//		
//		printArr(tree, 2 * N);
		br.close();
	}
	
	long init(int node, int start, int end){
		if(start == end){
			return tree[node] = arr[start];
		}
		else{
			return tree[node] = init(node * 2, start, (start+end)/2) + init(node*2+1, (start+end)/2+1, end);
		}
	}
	long sum(int node, int start, int end, int left, int right) {
	    if (left > end || right < start) {
	        return 0;
	    }
	    if (left <= start && end <= right) {
	        return tree[node];
	    }
	    return sum(node*2, start, (start+end)/2, left, right) + sum(node*2+1, (start+end)/2+1, end, left, right);
	}
	
	void update(int node, int start, int end, int index, long diff){
		if(index < start || index > end)	return;
		tree[node] = tree[node] + diff;
		if(start != end){
			update(node*2, start, (start+end)/2, index, diff);
			update(node*2+1, (start+end)/2+1, end, index, diff);
		}
	}
	void printArr(long [] arr, int n){
		for(int i = 0; i < n; i++){
			System.out.print(arr[i] + ", ");
		}
		System.out.println();
	}
}