[백준/JAVA] 2042번: 구간 합 구하기

🔺 문제

2042번: 구간 합 구하기

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static long[] tree; // 세그먼트 트리 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        int N = Integer.parseInt(st.nextToken());   // 데이터 개수
        int M = Integer.parseInt(st.nextToken());   // 변경 횟수
        int K = Integer.parseInt(st.nextToken());   // 구간 합 구한 횟수
        
        // 트리 배열 채우기 (구간 합)
        int treeHeight = 0;
        int len = N;
        while(len != 0) {
            len /= 2;
            treeHeight++;
        }
        
        int treeSize = (int)Math.pow(2, treeHeight + 1);
        int leftNodeStartIdx = treeSize / 2 - 1;    // 리프 노드 시작 idx
        tree = new long[treeSize + 1];
        
        for(int i = leftNodeStartIdx + 1 ; i <= leftNodeStartIdx + N ; i++) {
            tree[i] = Long.parseLong(br.readLine());
        }
        
        setTree(treeSize - 1);  // 트리 생성
        
        for(int i = 0 ; i < (M + K) ; i++) {
           st = new StringTokenizer(br.readLine()," ");
           long a = Long.parseLong(st.nextToken());     // 질의 유형
           int s = Integer.parseInt(st.nextToken());    // 시작 idx
           long e = Long.parseLong(st.nextToken());     // 종료 idx / 변경값
           
           // 업데이트
           if(a == 1) {
               changeVal(leftNodeStartIdx + s, e);
           }
           // 구간 합 계산
           else if(a == 2){
               s += leftNodeStartIdx;
               e += leftNodeStartIdx;
               
               System.out.println(getSum(s, (int) e));
           }
           else {
               return;
           }
        }
        br.close();
    }
    
    
    // 구간 합 계산 함수
    private static long getSum(int s, int e) {
        long partSum = 0;
        while(s <= e) {
           if(s % 2 == 1) {
               partSum += tree[s];
               s++;
           }
           if(e % 2 == 0) {
               partSum += tree[e];
               e--;
           }
           
           s /= 2;
           e /= 2;
        }
        
        return partSum;
    }
    
    
    // 값 변경 함수
    private static void changeVal(int idx, long val) {
        long diff = val - tree[idx];
        
        while(idx > 0) {
            tree[idx] += diff;
            idx /= 2;
        }
    }
    
    // 초기 트리 구성 함수
    private static void setTree(int i) {
        while(i != 1) {
            tree[i / 2] += tree[i]; // 각 노드 값을 부모 노드로 누적해 저장
            i--;
        }
    }
}

✅ 해결 아이디어
✔ 세그먼트 트리
- 값 변경이 빈번하게 일어나므로 세그먼트 트리 이용

 

 

---

🔺 다른 풀이들

[BOJ] 백준 2042번 : 구간 합 구하기 (JAVA)

[Java] 백준 2042번 구간 합 구하기

[JAVA/백준] 2042번: 구간 합 구하기

 

 

 

[JAVA] 세그먼트 트리 (Segment Tree)

---

💬 느낀 점

연습을 합시닷...

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 세그먼트 트리

41. 세그먼트 트리(Segment Tree)