[백준] 세그먼트 트리 모음(10868, 2357, 2042, 11505)

10868번: 최솟값 (acmicpc.net)

2357번: 최솟값과 최댓값 (acmicpc.net)

2042번: 구간 합 구하기 (acmicpc.net)

11505번: 구간 곱 구하기 (acmicpc.net)

 

 

4문제 다 세그멘트 트리 알고리즘 문제이다

순서대로 풀면 좋게 순서를 나열했다

나는 멋모르고 막 풀다보니 역순으로 풀었다 ㅎㅎ;; 11505 구간 곱 구하기를 못 풀겠어서 풀이를 보며 공부하다가 2042번을 알게 되고 이 문제도 풀이를 보며 공부하면서 풀고 10868 번을 보니깐 어떻게 접근해야될지 확 느낌이 오고 풀리는게 연습이 되는 느낌이였다

만약 처음 세그먼트 트리를 공부한다면 위에 올린 순서대로 풀어보면 좋지 않나 싶다.

 

4문제 다 세부적으로 풀이는 조금씩 다르지만 세그먼트 트리를 활용하여 풀어낼 수 있는 문제라는 점은 공통적이기에 이에 대해 적어보고자 한다.

 

누적합의 경우를 예를 들면,  전체 데이터 1~100에서 26~75 까지의 합을 구한다고 했을 때

이를 26+27+...+74+75으로 구하면 O(N) 연산을 하는 것이다

반면 세그먼트 트리를 만들어 놓는다면 

• 1~100의 합
  • => 1~50의 합
    • => 1~25의 합 (원하던 범위가 아니네? 재귀 멈춰!) 
    • => 26~50의 합 (원하던 범위네? return 950)
  • => 51~100의 합
    • => 51~75의 합 (원하던 범위네? return 1575) 
    • => 76~100의 합 (원하던 범위가 아니네? 재귀 멈춰!)

=> 950 + 1575 = 2525

이런 과정을 통해 O(logN)의 연산으로 답을 찾을 수 있게 된다.

// start: 시작, end: 마지막, left, right: 구하고자 하는 구간
    public static long interval_sum(int start, int end, int index, int left, int right){
        // 범위 초과한 경우
        if (left > end || right < start) {
		// 범위가 아니네? 재귀 멈춰! 
            return 0;
        }
        if (left <= start && right >= end) {
	//범위 안이네? 값 뱉어!
        // ex) left=26 right =75, start =26 end= 50 => return 950
            return segmentTree[index];
        }
        int mid = (start + end) / 2;
	// start 와 end 가 변하면서 우리가 구하고자 했던 left~right 구간을 조각조각 합쳐나가는 과정이다
        return interval_sum(start, mid, index * 2, left, right) + interval_sum(mid + 1, end, index * 2 + 1, left, right);
    }

그렇다면 처음 세그먼트 트리는 어떻게 초기화 하냐?

    public static long init(int start, int end, int index){
    // start == end 는 1~1, 2~2의 범위기에 segementTree[index] = arr[start == end]
        if (start == end) {
            return segmentTree[index] = arr[start];
        }
        int mid = (start + end) / 2;
		
        // index 노드의 왼쪽 자식 노드의 인덱스는 index*2, 오른쪽 자식 노드의 인덱스는 index*2+1
        return segmentTree[index] = init(start, mid, index * 2) + init(mid + 1, end, index * 2 + 1);
    }

재귀하면서 트리를 채워나가는데, 세그먼트 트리의 크기는  N개의 데이터로 만든다고 하였을 때 (보수적으로) 4*N의 크기를 잡으면 된다.

 

트리의 내용이 수정된다면 영향받는 트리의 부분들 수정을 해주어야 한다 => 구간 합 구하기, 구간 곱 구하기 문제에 추가된 개념

 // start: 시작 인덱스, end: 마지막 인덱스, what: 구간합을 수정해주고자 하는 노드, diff 수정 값
    public static void update(int start, int end, int index, int what, long diff) {

        // 수정하고자 하는 값이 탐색 범위 벗어나면 멈춰!
        if (what < start || what > end) {
            return;
        }

        segmentTree[index] += diff;
        
        // 끝 도달시 멈춰
        if (start == end) {
            return;
        }
        
        int mid = (start + end) / 2;
        update(start, mid, index * 2, what, diff);
        update(mid + 1, end, index * 2 + 1, what, diff);
    }

 

위에 예시로 올린 코드들은 구간 합 문제에서 사용한 코드들인데, 구간 곱에도 핵심은 같기에 응용하여 적용할 수 있다.