[백준문제풀이] 2042 구간 합 구하기 java 풀이

접근법 : 

**1) 어떻게 풀 것인가?**

인덱스드 트리의 기본적 문제이다.

문제에서 '구간합을 구해라' 라고 말한다. 

 

**2) 시간복잡도**

2초다.

인덱스드 트리를 사용하면 높이가 log(n) 이 되므로 위 과정은 

k 최댓값 10,000

n 최댓값 10^6

10,000(k) * log(10^6)으로, 180,000 정도되니 ㄱㅊ다.

 

**3) 공간복잡도**

256mb이다. 

입력으로 주어지는 모든 수는 -2^63보다 크거나 같고, 2^63-1보다 작거나 같은 정수이다.

라고 문제에서 나와있으므로 long을 가지는 몇가지만 조심한다.

 

**4) 풀면서 놓쳤던점**

 

**5) 이 문제를 통해 얻어갈 것**

인덱스드트리의 기초!

 

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[] strings = br.readLine().split(" ");
    	int n = Integer.valueOf(strings[0]);
    	int m = Integer.valueOf(strings[1]);
    	int k = Integer.valueOf(strings[2]);
    	int offset = 1;
    	
		for(offset =1; offset<n; offset *=2) {
		}
		long[]idxtree = new long[offset*2+2]; 
		
    	for(int i=0; i<n; i++) {
    		idxtree[offset+i] = Long.parseLong(br.readLine());
    	}
    	
    	for(int i=offset-1; i>=1; i--) {
    		idxtree[i] = idxtree[i*2] + idxtree[i*2+1];
    	}
    	
    	for(int i =0; i<m+k; i++) {
    		String[] strarr = br.readLine().split(" ");
    		int a = Integer.valueOf(strarr[0]);
    		int b = Integer.valueOf(strarr[1]);
    		long c = Long.valueOf(strarr[2]);
    		if(a == 1) {
    			int x = (int)(offset+b-1);
    			idxtree[x] = c;
    			while(x>1) {
    				x /=2;
    				idxtree[x] = idxtree[x*2] + idxtree[x*2+1];
    			}
    		}
    		else {
    			int l = (int)b+offset-1;
    			int r = (int)c+offset-1;
    			long ret = 0;
    			while(l <=r) {
    				if((l&1) == 1) {ret+= idxtree[l++];}
    				if((r&1) == 0) {ret+= idxtree[r--];}
    				l /=2;
    				r /=2;
    			}
    			sb.append(ret+"\n");
    		}
    	}
    	System.out.println(sb);
    }
}