백준 : 2042 ( 세그먼트 트리)

https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

세그먼트 트리의 초기화 변경 부분합을 구현하는 기초적인 문제.

package D0227;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class B2042 {
    static int N, M, K;
    static int arr[];
    static long node[];
 
    public static void main(String[] args) throws IOException {
        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());
        arr = new int[N + 1];
        node = new long[N * 4];
 
        for (int n = 1; n <= N; n++) {
            arr[n] = Integer.parseInt(br.readLine());
        }
        Init(1, N, 1);
        for (int m = 0; m < M + K; m++) {
            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) {
                int dif = c - arr[b];
                arr[b] = c;
                change(1,N,b,dif,1);
            } else {
                System.out.println(sum(1,N,b,c,1));
            }
 
        }
 
    }
 
    public static long Init(int start, int end, int n) {
 
        if (start == end) {
            return node[n] = arr[start];
        }
 
        int mid = (start + end) / 2;
 
        return node[n] = Init(start, mid, n * 2) + Init(mid + 1, end, n * 2 + 1);
    }
 
    public static long sum(int start, int end, int i, int j, int n) {
        if (j < start || end < i)
            return 0;
 
        if (i <= start && j >= end)
            return node[n];
 
        int mid = (start + end) / 2;
        return sum(start, mid, i, j, n * 2) + sum(mid + 1, end, i, j, n * 2 + 1);
    }
 
    public static void change(int start, int end, int b, int dif, int n) {
        // b번째 수를 c로 바꾼다
 
        if (start > b || end < b)
            return;
        
        if(b==start&&b==end) {
            node[n]+=dif;
            return;
        }
        
        
        if (b >= start && b <= end) {
            int mid = (start + end) / 2;
            
            change(start, mid, b, dif, n * 2);
            change(mid + 1, end, b, dif, n * 2 + 1);
            
            node[n] += dif;
            return;
        }
 
    }
}