BOJ_2042_구간 합 구하기 (Java)

[Gold I] 구간 합 구하기 - 2042

문제 링크

성능 요약

메모리: 102764 KB, 시간: 612 ms

분류

세그먼트 트리, 자료 구조

제출 일자

2024년 7월 31일 04:23:35

문제 설명

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.

입력

첫째 줄에 수의 개수 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(1 ≤ b ≤ N)번째 수를 c로 바꾸고 a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.

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

출력

첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -2⁶³보다 크거나 같고, 2⁶³-1보다 작거나 같은 정수이다.

문제풀이

세그먼트트리에서 update부분만 고려해보았다.

• 범위 밖이라면 종료
• 리프 노드시 변경
  • 해당 노드를 값을 변경하고 그 위 부모도 전부 합 새로 계산

코드

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

public class BOJ_2042_구간합구하기 {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int N, M, K;
	static long[] tree, num;

	public static void main(String[] args) throws IOException {
//        br = new BufferedReader(new InputStreamReader(System.in));
		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

		int treeHeight = (int) Math.ceil(Math.log(N) / Math.log(2));
		int treeSize = 1 << (treeHeight + 1);

		tree = new long[treeSize];
		num = new long[N+1];

		for (int i = 1; i <= N; i++) {
			num[i] = Long.parseLong(br.readLine());
		}
//		System.out.println(Arrays.toString(num));

		init(1, N, 1);

		for (int i = 0; i < M + K; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            long c = Long.parseLong(st.nextToken());

            if (a == 1) { // 숫자 업데이트
                update(1, N, 1, b, c);
                num[b] = c;
            } 
            else { // a==2 인 경우 - 합계산
                bw.write(sum(1, N, 1, b, (int) c) + "\n");
            }                       
            
        }
		
        bw.flush();
        bw.close();
        br.close();

	}

	/*
	 * 세그먼트 트리 초기화 
	 * node : 세그먼트 트리의 정점 번호 
	 * start : 이 정점이 관리하는 연속 구간의 왼쪽 끝 
	 * end : 이 정점이 관리하는 연속 구간의 오른쪽 끝
	 * 
	 */
	private static long init(int start, int end, int node) { // 최솟값 트리

		if (start == end) return tree[node] = num[start];

		int mid = (start + end) / 2;

        return tree[node] = init(start, mid, node*2) + init(mid + 1, end, node*2 + 1);

	}

	/*
	 * 세그먼트 트리 갱신 
	 * node : 세그먼트 트리의 정점 번호 
	 * start : 이 정점이 관리하는 연속 구간의 왼쪽 끝 
	 * end : 이 정점이 관리하는 연속 구간의 오른쪽 끝
	 * idx : 업데이트할 위치
	 * value : 새로 업데이트 할 값
	 * 
	 */	
	private static void update(int start, int end, int node, int idx, long value) {
		
        if (idx < start || end < idx) return;

		// 리프 노드시 변경
        if (start == end) {
            tree[node] = value;
            return;
        }
		
	    else {
	    	int mid = (start + end) / 2;
		        
	    	// 왼쪽자식구간
	        update(start, mid, node * 2, idx, value);
	        
	        // 오른쪽자식구간
	        update(mid + 1, end, node * 2 + 1, idx, value);		        

	        // 부모노드도 합 바뀌니까 자식 노드 업데이트 후 바뀐 자식 합으로 계산 다시해줌 
		    tree[node] = tree[node * 2] + tree[node * 2 + 1];
	    }

	        
	}
	
	// from ~ to 구간합
	private static long sum(int start, int end, int node, int from, int to) {
		
		// 덧셈 항등원 사용
		if (to < start || end < from) return 0;

        if (from <= start && end <= to) return tree[node];

        int mid = (start + end) / 2;
        
        return sum(start, mid, node * 2, from, to) + sum(mid + 1, end, node * 2 + 1, from, to);
	}
	
}