[ Baekjoon ][JAVA][2042] 구간 합 구하기

[www.acmicpc.net/problem/2042](https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

문제

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

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

출력

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

예제 입력

예제 출력

접근

상세해설 : gintrie.tistory.com/31

대표적인 세그먼트 트리 문제로 일단 유형과 흐름을 확실하게 외워두자!

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken());
        int m = Integer.parseInt(stk.nextToken());
        int k = Integer.parseInt(stk.nextToken());
        SegmentTree st = new SegmentTree(n); 
        for(int i=1; i<=n; i++){
            long v = Long.parseLong(br.readLine());
            st.update(i, v);
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<m+k; i++){
            stk = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(stk.nextToken());
            if(type==1){
                st.update(Integer.parseInt(stk.nextToken()), Long.parseLong(stk.nextToken()));
            } else {
                sb.append(st.getSum(Integer.parseInt(stk.nextToken()), Integer.parseInt(stk.nextToken()))).append('\n');
            }
        }
        System.out.print(sb);
    }
}

class SegmentTree{
    long[] tree;
    int s;
    
    public SegmentTree(int n){
        for(s = 1; s < n; s *= 2)
            ;
        tree = new long[s * 2];

        for(int i = 1; i < s + s; i++){
            tree[i] = 01;
        }
    }
    
    void update(int x, long v){
        int l = x + s - 1;
        tree[l] = v;
        l /= 2;
        while(l >= 1){
            tree[l] = tree[l * 2] + tree[l * 2 + 1];
            l /= 2;
        }
    }
    
    long getMin(int Left, int Right){
        int l = Left + s - 1, r = Right + s - 1;
        long rval = Long.MAX_VALUE;
        while(l <= r){
            if(l % 2 == 0)
                l /= 2;
            else {
                rval = Math.min(rval, tree[l]);
                l = (l / 2) + 1;
            }
            
            if(r % 2 == 1)
                r /= 2;
            else {
                rval = Math.min(rval, tree[r]);
                r = (r / 2) - 1;
            }
        }
        return rval;
    }
    
    long getSum(int Left, int Right){
        int l = Left + s - 1, r = Right + s -1;
        long rval = 0;
        while (l <= r){
            if(l % 2 == 0)
                l /= 2;
            else {
                rval += tree[l];
                l = (l / 2) + 1;
            }
            
            if(r % 2 == 1)
                r /= 2;
            else {
                rval += tree[r];
                r = (r / 2) - 1;
            }
        }
        return rval;
    }
}

 

 

++ 20/09/19 추가 코드 ( 위 코드보다 시간과 메모리는 조금 더 쓰지만, 가독성이 좋다 )

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] numbers = new int[1000001];
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		for(int i=1; i<=N; i++) {
			numbers[i] = Integer.parseInt(br.readLine());
		}
		SegmentTree sgTree = new SegmentTree(N);
		
		sgTree.init(sgTree.tree, numbers, 1, 1, N);
		
		int a, b, c;
		
		for(int i=0; i<M+K; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			
			if(a==1) {
				long thisNum = numbers[b];
				long diff = c - thisNum;
				numbers[b] = c;
				
				sgTree.update(sgTree.tree, 1, 1, N, b, diff);
			} else {
				System.out.println(sgTree.sum(sgTree.tree, 1, 1, N, b, c));
			}
		}
		
	}
}

class SegmentTree{
	long tree[];
	int treeSize;
	
	public SegmentTree(int arrSize) {
		// h = 트리 높이
		int h = (int) Math.ceil(Math.log(arrSize) / Math.log(2));
		this.treeSize = (int) Math.pow(2,  h + 1);
		tree = new long[treeSize];
	}
	
	// init 함수
	protected static long init(long[] tree, int[] nums, int node, int start, int end) {
		if(start == end) return tree[node] = nums[start];
		int mid = (start+end) / 2;
		return tree[node] = init(tree, nums, node*2, start, mid) + init(tree, nums, node*2 + 1, mid + 1, end);
	}
	
	// update 함수
	protected static void update(long[] tree, int node, int start, int end, int idx, long diff) {
		if(!(start<=idx && idx<=end)) return;
		tree[node] += diff;
		if(start != end) {
			int mid = (start + end) / 2;
			update(tree, node*2, start, mid, idx, diff);
			update(tree, node*2 + 1, mid + 1, end, idx, diff);
		}
	}
	
	// sum 함수
	protected static long sum(long[] tree, 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];
		int mid = (start + end) / 2;
		return sum(tree, node*2, start, mid, left, right) + sum(tree, node*2 + 1, mid + 1, end, left, right);
	}
			
}