세그먼트 트리 (구간합, 구간곱, 최소값, 최대값)

세그먼트트리가 처음에 봤을 때는 어려웠었는데

1년이 지나서 다시 보니까 별거 아니다.

백준 세그먼트트리 - 42 문제

 

특정 구간의 최소값을 구하는데, 질문이 1개면 그냥 일일이 세면 된다.

질문이 10만개면 달라진다.

메모이제이션을 해야 하는데, 세그멘테이션 트리를 이용한다.

   

N = 8, value = [2,1,5,3,2,4,10,5] 에서 구간 최소값 을 구하는 Segment tree

leaf Node가 N개 구성된다. ( tree[8] ~ tree[15] )

사실, 2^(HEIGHT-1) 이다. 따라서, N이 7일 때도 leaf는 8개

   

트리 어떻게 만드나?

초기화

final int HEIGHT = (int) Math.ceil(Math.log(N) / Math.log(2)) + 1; // 4
final int S = Math.pow(2,HEIGHT-1) // 8

long[] tree = new long[S * 2];
Arrays.fill(tree,Integer.MAX_VALUE); // 최소값을 넣어줄 것이기 때문에 높은 값으로 초기화.

 

leaf 노드에 값을 넣어준다. (tree[8] ~ tree[15])

values = {2,1,5,3,2,4,10,5}

for(int i = 0; i < N; i++) {
    index = Math.pow(2,HEIGHT-1) + i;
    tree[index] = values[i];
}

 

parents 구하기 (tree[1] ~ tree[7])

for(int i = S-1; i >= 1;i--) { // 7 6 5 4 3 2 1
    int leftChild = i * 2;
    int rightChild = i * 2 + 1;
    
    tree[i] = Math.min(leftChild, rightChild);
}

값 초기화에는 여러 방법들이 있다. Top-down 방식보다 위 방법이 더 효율적임.

   

구간 최소값 구하기.

구간의 최소값 트리를 만들었다.

1 ~ 4 최소값 또는 5 ~ 6 최소값을 직접 세지 않아도 메모이제이션 되어 있다.

 

2 ~ 5 최소값은 어떻게 구하는가.

min(2, 3~4, 5) 로 해결하면 된다.

 

하늘색 부분은 return 잘 시켜주면 됨.

 

private long get(int idx, int l, int r, int from, int to) {
    if(index >= tree.length-1) return Integer.MAX_VALUE; // tree idx 범위 밖
    if(r < FROM || l > TO) return Integer.MAX_VALUE; // l ~ r 이 2 ~ 5와 겹치지 않음.
    else if(FROM <= l && TO >= r) return tree[idx]; // l ~ r이 2 ~ 5 에 완전포함

    // l ~ r 이 2 ~ 5 와 부분적으로 겹칠 경우 아래 코드 수행

    int mid = (l + r) / 2;

    return Math.min(get(idx*2, l, mid, int from, int to), get(idx*2 + 1, mid+1, r, from, to));
}

위 코드의 4번째 줄에서 return하는 경우는 3가지다.

1. l = 2, r = 2
2. l = 3, r = 4
3. l = 5, r = 5

 

( 최대값의 경우 max 이고, 구간합은 덧셈, 구간곱은 곱셈을 해주면 된다. )

   

update ?

기존의 노드를 바꿔야 하는 경우가 있다.

초기화와 똑같다.

// ex) 2번째 값을 10으로 바꾼다.  [2,1,5,3,2,4,10,5] -> [2,10,5,3,2,4,10,5]
    int idx = 2;
    int value = 10;

    update(2,10);

    //...

private void update(int idx, int value) {
    int idx += S - 1; // 2번째 값은 tree의 index상으로 9임.
    tree[idx] = value;
    idx /= 2;

    while(idx >= 1) {
        int leftChild = idx * 2;
        int rightChild = idx * 2 + 1;

        tree[idx] = Math.min(tree[leftIdx], tree[rightIdx]);

        idx /= 2;
    }
}

   

value 범위가 int 범위를 초과하는지 항상 확인 할것.

   

문제 잘 읽자…

세그먼트 문제를 풀면서 런타임 에러도 뜨고, 많이 틀렸다.

역시나 문제를 잘못 읽었다…

습관이 참 무섭다. 집이라고 대충대충 보면 안되겠다.

 

오픽 시험이 이틀 남았는데, 영어 공부하기가 너무 귀찮아서 세그먼트를 풀었다..

Sorry, Eva….