[알고리즘] 세그먼트 트리 (Segment Tree)

구간 합을 더 빠르게 구하는 방법,

구간 합을 구하는 방법을 생각해 보자, A[1:10]까지의 배열 합 ? → O(n), 만약 n이 엄청나게 크다면 ,, ? → O(log n)만에 구간 합을 구하는 방법을 생각해 보자 😁

구간합을 구하는 세그먼트 트리 예시

다음과 같은 트리를 만들자, 트리의 부모 노드는 항상 '합'을 저장하고 있다.

세그먼트 트리 만들기

위의 트리에서 11개의 노드를 저장하기 위해서 32개의 배열을 사용하고 있다. (트리 저장하는 방법 아시죠?) N개의 노드를 저장하기 위해서 넉넉하게 4*N개의 배열을 할당하는 것으로 시작하면 된다.

구간합을 구하기 위한 세그먼트 트리를 만드는 것은 재귀적으로 구현할 수 있다.

int A[11] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
int tree[40]

int init(int index, int start, int end){
        if(start > N) return 0;
    if (start == end)
        tree[index] = A[start];
    else{
        int mid = (start+end)/2;
        tree[index] = init(index*2, start, mid) + init(index*2+1, mid+1, end);
    }
    return tree[index];
}

int main(){

        int N = 10;
        int height = ceil(log2(N));
        int last = pow(2,(height));
            // 1번부터 10번까지의 배열로 세그먼트 트리를 만들어보장
        init(1, 1, last);

        return 0;
}

세그먼트 트리로 구간합 구하기

세그먼트 트리는 항상 재귀적이다, 그리고 게으르다! 다음번에 대신 구해주길 바란다. 재귀함수를 작성할때처럼 항상 종료 조건을 잘 작성하자

• tree[index]가 start부터 end까지의 합을 의미할 때, left부터 right까지의 구간 합을 구하여라

int sum(int index, int start, int end, int left, int right){
    // ~left~right~start~end 일 경우
        // ~start~end~left~right 일 경우
    if (start > right || end < left)
        return 0;
        // ~left~start~end~right 일 경우
    else if (start >= left && right <= end)
        return tree[index];
    else { //애매하게 걸쳐있는 경우
        int mid = (start+end) / 2;
                //내 자식들에게 알아서 계산하도록 맡기자 !!!
        return sum(index*2, start, mid, left, right) + sum(index*2+1, mid+1, end, left, right);
    }
}

//A[3]부터 A[10]까지의 합 구하기, 다음과 같이 함수를 부르면 되겠죠?
int ans = sum(1, 1, last, 3, 10)

이게 시간 복잡도가 log2(n)이 된다는 게 느낌이 오시나욥 ?

세그먼트 트리에서 값 변경하기

값을 변경하고 싶다면 그 위까지, 루트 끝까지 모두 변경해야 할 것 입니다. 이것도 마찬가지로 재귀적으로 바꾸어줍니다. 값을 변경했을 때의 차이만큼 모두 업데이트 해주면 됩니다.

// tree[index]는 start부터 end까지의 합을 의미한다
// A[changed_index] 값이 diff 만큼 더해줄 값을 변경되었다면 다음과 같이..!!
void update(int changed_index, int diff, int index, int start, int end){
    //changed_index가 start~end 범위 밖이라면? 값을 변경해줄 필요가 없다
        if (changed_index < start || changed_index > end)
        return;

        //범위 안이라면 무조건 변경
    tree[index] += diff;

    if (start != end){
        int mid = (start+end) / 2;
        update(changed_index, diff, index*2, start, mid);
        update(changed_index, diff, index*2+1, mid+1, end);
    }
}

//예를 들어서 A[3]을 100으로 변경해볼까욥
update(3, -A[3] + 100, 1, 1, last);

하나의 값을 변경 할때의 시간 복잡도는 어떻게 될까요? => 트리의 높이인 O(logN)만큼의 시간 복잡도를 가진다

 

🦔 백준 풀어볼 문제들

2042 구간 합 구하기
2357 최솟값과 최댓값
1725 커피숍2 구간합 + 값 업데이트 하기
6549 히스토그램에서 가장 큰 직사각형 어려워요