세그트리 메모리 최적화

보통 세그먼트 트리를 구현할 때는 포화 이진 트리 구조를 사용합니다. 이해하기에 직관적이기도 하고, 초기에 작성된 알고리즘 설명글들이 포화 이진 트리를 기준으로 한 것이 크게 영향을 끼치지 않았나 싶습니다.

이 경우, 리프노드의 개수는 n보다 크거나 같은 2의 멱수 중 최솟값인 sz로 설정하며, tree배열의 크기는 2*sz가 됩니다.

int sz = 1;
while (sz < n) sz <<= 1;
tree.resize(sz << 1);

이러한 계산을 생략하고 싶을 때는 tree배열의 크기를 4*n으로 넉넉하게 잡고, sz의 값을 몰라도 되는 top-down방식으로 구현하는 것이 ps에서 일종의 관례가 된 것 같습니다.

 

하지만 세그먼트 트리를 반드시 모든 레벨이 꽉 찬 포화 이진 트리로 구현할 필요는 없습니다. 불필요한 더미 노드를 제거하고 full binary tree의 성질만 유지한다면 tree배열의 크기를 $2n$으로 최적화할 수 있습니다.

 

이진트리에서 자식이 없는 노드(리프노드)가 $n_0$개, 자식이 하나인 노드가 $n_1$개, 자식이 둘인 노드가 $n_2$개라고 합시다.

트리에 존재하는 전체 정점의 개수는 $n_0+n_1+n_2$개입니다.

각 노드가 가진 자식간선의 개수를 합하면 총 간선 수는 $n_1 + 2n_2$개인데, 트리에서 전체 간선의 수는 정점의 개수보다 1 작기 때문에 아래의 식이 성립합니다.

$n_0+n_1+n_2 - 1 = n_1 + 2n_2$

$n_2 = n_0 - 1$

세그먼트트리에서 $n_1 = 0$이고, 따라서 총 노드의 개수는 $n_0 + n_1 + n_2 = 2n_0 - 1$개입니다.

 

구현상 편의를 위해 루트노드의 번호를 1에서 시작하므로 tree배열의 크기는 $2n$으로 설정하면 됩니다.

constexpr int INF = 21e8;
struct Seg {
    int n;
    vector<int> tree;
    Seg(int n) : n(n), tree(2 * n, -INF) {}
    void update(int i, int val) {
        tree[i += n - 1] = val;
        while (i >>= 1) tree[i] = max(tree[i << 1], tree[i << 1 | 1]);
    }
    int query(int l, int r) {
        int res = -INF;
        for (l += n - 1, r += n - 1; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) res = max(res, tree[l++]);
            if (~r & 1) res = max(res, tree[r--]);
        }
        return res;
    }
};