일반화 세그먼트 트리 구현 - 2. 초기화와 생성자 구현

일반화 세그먼트 트리 구현 - 1. 일반화 프로그래밍이란?

 

저번 글에 이어서 이번에는 세그먼트 트리의 생성자와 초기화 부분을 구현해보았다.

 

1. 멤버 변수

 

세그먼트 트리의 구조체를 만든다면 필요한 멤버 변수가 뭐가 있을지 생각해보았다.

 

① 트리로 사용할 vector

② 쿼리를 처리하기 위해 필요한 원본 배열의 시작점과 끝점의 index

③ 두 구간의 값을 합할 때 사용할 함수의 포인터

 

따라서 아래와 같이 구조체를 만들어 주었다. 

template<typename T> struct segment_tree {
    
    T (*merge)(T, T);
    int s,e;
    vector<T> tree;
    
} //T는 노드에 저장할 값의 자료형

 

2. 생성자

 

세그먼트 트리를 생성할 때 매개 변수로 필요한 값들을 받아 구조체의 멤버 변수들을 초기화 하도록 생성자를 구현했다.

매개 변수로는 원본 배열의 참조자, 시작점과 끝점의 인덱스, 값을 합할 때 사용할 함수의 포인터를 사용했다.

segment_tree(vector<T> &vec,int start,int end,T (*func)(T, T)) {
        s=start;
        e=end;
        merge=func; 
        tree.resize(4*(e-s+1)+1);
        init(vec,1,start,end); //이후 만들 트리를 초기화하는 함수
}

 

3. 트리 초기화

 

매개변수의 값을 기반으로 트리를 초기화 하는 함수를 만들었다.

T init(vector<T> &vec,int node,int start,int end) {
        if(start==end) return tree[node]=vec[start];
        int mid=(start+end)/2;
        return tree[node]=merge(init(vec,node*2,start,mid),init(vec,node*2+1,mid+1,end));
}

 

 

다음 글에서는 트리를 업데이트하는 함수와 쿼리를 처리하는 함수를 만들어 세그먼트 트리를 완성해보겠다.