[BOJ]2042. 구간 합 구하기

# 문제링크

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

# 알고리즘

- Segment Tree를 사용해서 풀어야 한다.

- https://palyoung.tistory.com/64

# 풀이

package segment;
 
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int N, M, K;
    static int arr[];
    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("src\\sample.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        arr = new int[N];
        int a=0, b=0, c=0;
        
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        SegmentTree seg = new SegmentTree(arr, N);
        //seg.print();
        
        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());
            
            // segment tree 업데이트
            if (a == 1) {
                seg.update(b-1, c, 1, 0, N-1);
            }
            // segment tree에서 구간의 합 
            else if (a == 2) {
                sb.append(seg.query(b-1, c-1, 1, 0, N-1)+"\n");
            }
        }
        System.out.println(sb);
    }
}
 
class SegmentTree {
    long SegmentTreeArr[];    // segment tree node 데이터
    
    SegmentTree(int arr[], int N) {
        SegmentTreeArr = new long[N*4];
        init(arr, 0, N-1, 1);
    }
    
    // Leaf Node가 N개인 Segment Tree 생성
    // node 의 왼쪽 자식은 node*2, 오른쪽 자식은 node*2+1
    long init(int arr[], int left, int right, int node) {
        // node가 리프 노드인 경우
        if (left == right) return SegmentTreeArr[node] = arr[left];
        int mid = (left+right)/2;
        return SegmentTreeArr[node] = init(arr, left, mid, node*2) + init(arr, mid+1, right, node*2+1);
    }
    
    // Segment Tree를 갱신하고 노드 구간의 합을 구한다.
    long update(int index, int value, int node, int nodeLeft, int nodeRight) {
        // index가 Node 구간에 포함되지 않는 경우
        if (index < nodeLeft || index > nodeRight) return SegmentTreeArr[node];
        
        // node가 리프 노드인 경우
        if (nodeLeft == nodeRight)  return SegmentTreeArr[node] = value; 
        
        int mid = (nodeLeft + nodeRight)/2;
        return SegmentTreeArr[node] = update(index, value, node*2, nodeLeft, mid) + update(index, value, node*2+1, mid+1, nodeRight); 
    }
    
    // Segment Tree의 구간 합을 구한다.
    long query(int left, int right, int node, int nodeLeft, int nodeRight) {
        // 두 구간이 겹치지 않는 경우
        if (left > nodeRight || right < nodeLeft) return 0;
        
        // [left, right]가 [nodeLeft, nodeRight]를 포함하는 경우
        if (left <= nodeLeft && right >= nodeRight) return SegmentTreeArr[node];
        
        int mid = (nodeLeft + nodeRight)/2;
        return query(left, right, node*2, nodeLeft, mid) + query(left, right, node*2+1, mid+1, nodeRight); 
    }
    
    void print() {
        for (int i=0; i<SegmentTreeArr.length; i++) {
            System.out.printf("%d, ", SegmentTreeArr[i]);
        }
        System.out.println();
    }
}