인덱스 트리 (Indexed Tree)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	/*
     * 구간 합 구하기
	 * https://www.acmicpc.net/problem/2042
	 */
	public static void main(String[] args) throws IOException {
		/*
		 * 첫째 줄에 수의 개수 N(1<=N<=1,000,000)과 M(1<=M<=10,000), K(1<=k<=10,000) 가
		 * 주어진다. M은 수의 변경이 일어나는 회수이고, K는 구간의 합을 구하는 회수이다. 그리고 둘째 줄부터 N+1번째 줄까지
		 * N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a,b,c가 주어지는데, a가 1인
		 * 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 합을 구하여 출력하면 된다.
		 */

		//System.setIn(new FileInputStream("res/algo1/C.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer ST = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(ST.nextToken());
		int M = Integer.parseInt(ST.nextToken());
		int K = Integer.parseInt(ST.nextToken());
		
		/*
		 * 1. 트리 상단의 크기 구함
		 * 2. 그다음부터 값을 받음
		 * 3. 트리상단의 값을 넣음(덧셈) (부모index = 자식index / 2)
		 * 4. update : 변경값을 부모에게 계속 업데이트함
		 * 5. search : 대표값 찾아서 더하기
		 * 5.1 left에서 우측이 대표값 : 홀수 (idx) -> 우측위
		 * 5.2 right에서 좌측이 대표값 : 짝수 (idx) -> 좌측위
		 * 6. cross전까지 반복
		 */
		
		long[] A = new long[4*N];
		
		//1. 트리 상단의 크기 구함
		int size = 0;
		for (size = 1; size <= N; size*=2);
		size--;
		
		//2. 그다음부터 값을 받음
		for (int i = 1; i <= N; i++) {
			A[size+i] = Integer.parseInt(br.readLine());
		}
		
		//3. 트리상단의 값을 넣음(덧셈) (부모index = 자식index / 2)
		for (int i = size; i >= 1; i--){
			A[i] = A[i*2] + A[i*2+1];
		}
		
		
		for (int i = 1; i <= M+K; i++){
			ST = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(ST.nextToken()); //QUERY : b -> c , or b ~ c 합
			int b = Integer.parseInt(ST.nextToken()); 
			int c = Integer.parseInt(ST.nextToken());
			
			if (1 == a){//4. update : 변경값을 부모에게 계속 업데이트함
				long gap = c - A[size+b];
				A[size+b] = c;
				int pos = (size+b)/2;
				while(pos >= 1){
					A[pos] = A[pos]+gap;
					pos /= 2;
				}
				//System.out.println(A[1]);
			} else if (2 == a){ //5. search : 대표값 찾아서 더하기
				
				long ans = 0;
				int l = b+size;
				int r = c+size;
				while (l <= r){
					if (l%2 == 1) {
						ans += A[l];
					} 
					l ++;
					l /= 2;
					
					
					if (r%2 == 0){
						ans += A[r];
					}
					r --;
					r /= 2;
					
				}
				bw.write(ans+"\n");
			}
		}
		
		br.close();
		bw.flush();
		bw.close();

	}

}

* 클래스화

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

public class Main_d1_2042 {
	/*
	 * 구간 합 구하기
	 * https://www.acmicpc.net/problem/2042
	 */

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		/*
		 *  N(1<=N<=1,000,000)과 M(1<=M<=10,000), K(1<=k<=10,000) 
		 */
		
		st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken()); //노드개수
		int M = Integer.parseInt(st.nextToken()); //수의 변경 횟수
		int K = Integer.parseInt(st.nextToken()); //합을 구하는 횟수
		
		
		IndexTree it = new IndexTree(N);
		
		for (int i = 1; i <= N; i++) {
			int val = Integer.parseInt(br.readLine());
			it.set(i, val);
		}
		
		for (int i = 1; i <= M+K; 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 == 1) {
				it.set(b, c);
			} else {
				long result = it.search(b, c);
				bw.write(result+"\n");
			}
		}		
		
		br.close();
		bw.flush();
		bw.close();
	}
	
	
	static class IndexTree {
		
		int sz = 0;
		long[] tree;
		
		IndexTree(int n){
			
			for (sz = 1; sz <= n; sz *= 2);
			tree = new long[sz*2];
			sz--;
		}
		
		
		void init (int idx, long val) {
			idx += sz;
			tree[idx] = val;
			while(idx >= 1) {
				idx /= 2;
				tree[idx] = tree[idx*2] + tree[idx*2+1]; 
			}
		}
		
		void set (int idx, long val) {
			idx += sz;
			long gap = tree[idx] - val;
			while(idx >= 1) {
				tree[idx] -= gap;
				idx /= 2;
			}
		}
		
		long search (int l, int r) {
			l += sz;
			r += sz;
			
			long result = 0;
			while (l <= r) {
				
				if (l%2 == 1) {
					result += tree[l];
				}
				l++;
				l /= 2;
				
				if (r%2 == 0) {
					result += tree[r];
				}
				r--;
				r /= 2;
			}
			
			return result;
		}
	}
}