[백준] 2042 구간 합 구하기

문제링크 : www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

예전에 세그먼트 트리(인덱스 트리) 문제 기본 문제로 풀어봤던 문제를 다시 풀어봤다.

재귀 대신 반복으로 할 수 있으면 반복으로 하는 편이다.

예전 SDS 알고리즘 심화 특강 때, 강사분이 푸셨던 재귀가 아닌 방법을 기억해보며 코드를 짰다.

 

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

public class Main {
	public static int N,M,K; // 노드수,변경수, 쿼리 수
	public static int reaf_start; //리프 노드중 가작 왼쪽에 있는 노드 번호
	public static long tree[];
	
	public static void update_tree(long val,int reaf_idx) {
		long diff = val - tree[reaf_idx]; 
		while(reaf_idx!=0) {
			tree[reaf_idx] += diff;
			reaf_idx /=2;
		}
	}
	
	// left ~ right까지의 부분 합 쿼리
	public static long query(int left, int right) {
		left += reaf_start -1;
		right += reaf_start-1;
		long sum = 0;
		while(left<=right) {
			if(left %2 ==1) {
				sum+= tree[left];
				left+=1;
			}
			if(right%2==0) {
				sum+= tree[right];
				right-=1;
			}
			left /= 2;
			right /=2;
		}
		return sum;
	}
	
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		reaf_start =1;
		while(true) {
			if(reaf_start >= N) {
				break;
			}
			reaf_start*=2;
		}
		
		tree = new long[reaf_start*2];
		
		for(int i=0;i<N;i++) {
			int num =  Integer.parseInt(br.readLine());
			update_tree(num,i+reaf_start);
		}
		
		for(int i=0;i<M+K;i++) {
			st = new StringTokenizer(br.readLine());
			int order = Integer.parseInt(st.nextToken());
			int left = Integer.parseInt(st.nextToken());
			int right = Integer.parseInt(st.nextToken());
			if (order == 2)
				System.out.println(query(left,right));
			else {
				update_tree(right, left + reaf_start-1);
			}
		}
	}

}