세그먼트 트리

(재귀) 세그먼트 트리는 Complete Binary Tree로 배열을 사용해서 구현한다.
(비재귀 구현은 Leaf 레벨도 다 채워지는 Full Binary Tree로 구현)

---

Seg Tree를 구현하는 배열 사이즈에 대한 고찰

 

사이즈 N인 배열 a가 주어졌다고 하자 (ex. a = [2, 4, 6, 9, 7])
배열 a에 들어있는 수는 모두 세그먼트 트리의 Leaf node에 들어가게 된다.

그럼 세그먼트 트리를 만드는 배열 tree의 크기는 얼마가 되어야 할까?

1. N이 2의 제곱 꼴인 경우에는 2*N - 1개;
왜? 맨 위 루트 노드부터 아래로 내려갈수록 노드 개수가 2배가 되므로, 1 + 2 + 2^2 + ... + N (= 2^H)
2^H = N 이므로, 트리의 깊이 H = log2(N)

2. N이 2의 제곱 꼴이 아닌 경우;
Perfect binary tree의 각 level h에는 2^h개의 노드가 있다 (root h = 0 라고 할 때)
세그먼트 트리의 Leaf에 적어도 N개 노드가 있어야 하므로,

 

N <= 2^H   (N : number of leaf nodes)

log2(N) <= H

∴ H = tree_depth = ceil(log2(N))

 

Leaf 노드가 2^H개 필요하므로, 등비수열의 합에 의해
전체 세그먼트 트리에는 총 2^(H+1) - 1개의 노드가 필요함

ex. N = 17 이라고 하면, H = ceil(log2(17)) = 5
N개의 수를 모두 담으려면, Leaf 노드가 총 2^H = 32개 있어야 한다. 
* 32 - 17 = 15개가 남는데, 답에 영향을 주지 않는 값으로 초기화하고 사용하지 않는다.

전체로는 총 2^6 - 1 = 63개의 노드가 필요함.

void construct(vector<long long>& arr) {
  const int H = int(ceil(log2(arr.size())));
  const int TREE_SIZE = 1 << (H + 1);
  tree = vector<long long>(TREE_SIZE, INIT); // 1-indexing이라 TREE_SIZE-1이 아닌 그대로

  ARR_SIZE = arr.size() - 1;
  init(arr, 1, 0, ARR_SIZE);
}

 

---

'트리' 아니랄까봐, 재귀 구현이 보편적이긴 하나,

'Perfect' Binary Tree를 항상 만족시켜줄때 Bottom-up iteration 구현도 가능한 것으로 보임.

(즉, Leaf 노드 개수를 2의 제곱 꼴로 맞춰줄 때만)

 

코드 업데이트 안됨. snippet이 최신

// Top-down (재귀) 구현

// 1. Segment Tree Initialization
/*
// a: 배열 a
// tree: 세그먼트 트리
// node: 세그먼트 트리 노드 번호
// node가 담당하는 배열 a의 범위; [start, end]
반환 값 : a의 [start, end] 구간 합

O(M) where M = total # of nodes in 'tree'

장점) a size가 2의 거듭제곱 꼴이 아니면 tree의 모든 노드를 사용하진 않음; 
end = a.size() - 1로 설정 가능

Usage
See below 'main'
*/
long long init(vector<long long> &a, vector<long long> &tree, int node, int start, int end) {
    if (start == end) return tree[node] = a[start];
	else {
    	int LEFT_CHILD = node*2, RIGHT_CHILD = node*2+1, mid = (start+end)/2;
        return tree[node] = init(a, tree, LEFT_CHILD, start, mid) 
        					+ init(a, tree, RIGHT_CHILD, mid+1, end);
    }
}


// 2. Query (look-up, value retrieval)
/*
node가 담당하는 구간이 start~end이고, 구해야하는 합의 범위는 left~right
반환 값 : a의 [left, right] 구간 합

O(logN)

Usage
a = [2, 4, 6, 9, 7]
Query for idx range [1, 3]
→ query(seg_tree, 1, 0, a.size()-1, 1, 3)
*/
long long query(vector<long long> &tree, int node, int start, int end, int left, int right) {
    // Case 1. [left, right] 와 [start, end]가 아예 겹치지 않음 → 탐색할 이유가 없음. 그냥 return
    if (left > end || right < start) return 0;

    // Case 2. [left, right] 가 [start, end]를 완전히 포함하는 경우
    // ex) (N = 16) [3, 9] 구간 합 찾는데, 현재 노드는 [4, 7] 구간 합 정보 담고 있음 → 그 정보 return 
    if (left <= start && end <= right) return tree[node];

    // 현재는 구간 합 정보를 담기 위해 '+' 사용
    const int LEFT_CHILD = node*2, RIGHT_CHILD = node*2+1, mid = (start+end)/2;
    return query(tree, LEFT_CHILD, start, mid, left, right) 
    		+ query(tree, RIGHT_CHILD, mid+1, end, left, right);
}


// 3. Update value
/*
// Top-down (recursion)
// index : 업데이트할 a 원소의 index (a의 몇 번째 원소)
// diff = val - a[index] : 바꿀 값 - 기존 값

Root 부터 시작해서 [index, index] 구간을 담당하는 Leaf 노드까지 재귀 탐색하며 diff를 더해줌
O(logN)

Usage
a = [2, 4, 6, 9, 7]
Updating 4th element (index 3) to 14 (val)
→ update(seg_tree, 1, 0, a.size()-1, index, val-a[index])
*/
void update(vector<long long> &tree, int node, int start, int end, int index, long long diff) {
    if (index < start || index > end) return;
    tree[node] = tree[node] + diff;
    if (start != end) {
        update(tree,node*2, start, (start+end)/2, index, diff);
        update(tree,node*2+1, (start+end)/2+1, end, index, diff);
    }
}

int main(){
    //vector<long long> a{ 1, 2, 3, 4, 5, 6, 7, 8 };
    vector<long long> a{ 2, 4, 6, 9, 7, 10 };

    const int H = int(ceil(log2(a.size())));
    const int TREE_SIZE = 1 << (H + 1);
    vector<long long> seg_tree(TREE_SIZE);

    // ★ end로 a.size() - 1 이 들어감
    init(a, seg_tree, 1, 0, a.size() - 1);
    cout << query(seg_tree, 1, 0, a.size() - 1, 1, 3) << "\n";

    int val = 10, idx = 2;
    update(seg_tree, 1, 0, a.size() - 1, idx, val - a[idx]);
    a[idx] = val;

    cout << query(seg_tree, 1, 0, a.size() - 1, 1, 3) << "\n";
}

 

Top-down 식 재귀 구현

www.acmicpc.net/blog/view/9

세그먼트 트리 (Segment Tree)

---

// Bottom-up (비재귀)

/*
먼저 tree의 Leaf 노드들을 a의 값들로 채우고, 위로 올라가면서 초기화

O(M/2) where M = total # of nodes in 'tree'

WARNING) 'tree' nodes must be initialized prior

장) 호출 형태가 재귀에 비해 간단, 전체 노드의 반만 탐색
단) 원소 개수가 2의 거듭제곱 꼴이 아닐때도 Full binary tree 전체 사용
end = 'Leaf노드 개수' 로만 설정해야 함
*/
void init(vector<long long> &a, vector<long long> &tree){
	const int H = int(ceil(log2(a.size())));
	const int CHILD_IDX_START = 1<<H;

	// 1. Initialize tree leaf nodes
    for (int idx = 0; idx < a.size(); idx++)
        tree[idx + CHILD_IDX_START] = a[idx];

	// 2. Move up each level and initialize nodes using its children
    for(int i = CHILD_IDX_START - 1; i > 0; i--)
        tree[i] = tree[i*2] + tree[i*2+1]; // 구간 합의 경우
}


/*
// i : 업데이트할 a 원소의 index (a의 몇 번째 원소)

Usage
a = [2, 4, 6, 9, 7]
Updating 4th element (index 3) to 14 (val)
→ update(a, seg_tree, index, val)
*/
void update(vector<long long> &a, vector<long long> &tree, int i, int val){
    // 실제 세그먼트 트리 배열에서 바꿀 리프 노드의 인덱스 찾기
    /*
    H = ceil(log2(N))
    Leaf 노드 : 2^H개
    전체 노드 개수 : 2^(H+1)-1개 이므로, Leaf 노드 위 레벨에 모두 2^H - 1개의 노드 있음. 

    즉, Leaf노드는 세그먼트 트리 배열 상에서 index = 2^H 부터 시작함 (1-indexing)
	*/
	const int H = int(ceil(log2(a.size())));
    i += (1<<H); 

    tree[i] = val;
    while(i > 1){ // i == 1 : root node
        i /= 2;
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    a[i] = val; // change real array 'a'; may be deleted
}	

int main(){
    //vector<long long> a{ 1, 2, 3, 4, 5, 6, 7, 8 };
    vector<long long> a{ 2, 4, 6, 9, 7, 10 };

    const int H = int(ceil(log2(a.size())));
    const int TREE_SIZE = 1 << (H + 1);
    
    const int INIT = 0;
    vector<long long> seg_tree(TREE_SIZE, INIT);
    init(a, seg_tree);

    // ★ Query에서, End 값으로 leaf 노드의 개수 (1 << H) - 1 이 들어감을 체크
    // [0, a.size()-1]이 아니라, [0, Leaf 노드 개수 - 1]이 돼야함.
    cout << query(seg_tree, 1, 0, (1 << H) - 1, 1, 3) << "\n";
    update(a, seg_tree, 2, 10);
    cout << query(seg_tree, 1, 0, (1 << H) - 1, 1, 3) << "\n";
}

 

Bottom-up 식 iteration 구현

blog.naver.com/kks227/220791986409

세그먼트 트리(Segment Tree) (수정: 2019-02-12)

 

더 깔끔한 비재귀 코드는 아래를 참고

(그냥 코드만 봐서는 이해 못함. 직접 예제 돌려보거나 인터넷 검색해서 직접 구현해보기)

 

www.geeksforgeeks.org/iterative-segment-tree-range-minimum-query/

Iterative Segment Tree (Range Minimum Query) - GeeksforGeeks

blog.naver.com/jinhan814/222147466010

[BOJ] 2042번 - 구간 합 구하기

justicehui.github.io/koi/2019/03/03/BOJ2517/

백준2517 달리기

---

<더 공부할 요소>

- 위 코드를 보면, 함수들의 인자가 복잡하게 들어가서 쓰기 까다로운데,

Seg_Tree class/struct을 만들어서 인터페이스를 짜보자.  

(tree 배열, init/query/update raw 코드 및 wrapper들)

 

- 비재귀 코드 공부

 

- 대회에 쓰이는 다양한 Segment Tree variation이 있다

cp-algorithms.com/data_structures/segment_tree.html

Segment Tree - Competitive Programming Algorithms