Segment-Tree

구간 데이터를 로그시간안에 관리할 수 있는 자료구조인 세그먼트 트리에 대해서 알아보겠습니다.

세그먼트 트리

세그먼트트리는 데이터가 다수 주어지고 구간 연산을 반복적으로 하는 경우에 주로 사용합니다.
대표적인 예시로 구간합을 계산하는 경우를 들 수 있습니다.
물론 구간합을 구하는 것은 누적합 Prefix-Array를 통하여 더 쉽게 계산할 수도 있습니다.
그러나 누적합을 사용하면 값을 변경할 때 $O(N)$ 시간이 걸리게 되어, 빈번한 값 변경이 있는 경우에 적합하지 않습니다.
그래서 보통 세그먼트트리는 빈번한 값 변경을 동반하는 경우에 자주 쓰이게 됩니다.
세그먼트트리는 구간을 두개의 하위구간으로 나누고, 다시 각 구간을 두개의 하위구간으로 나누는 것을 반복하여 최종적으로 각 원소로 나누어질 때까지 나누고, 이진트리에 값을 미리 계산해두는 자료구조입니다.
이로 인하여 메모리 측면에서 데이터의 두배만큼 공간을 차지하게 됩니다.
메모리를 더 사용하는 대신, 구간값 계산에는 $O(logN)$이 걸리고, 값 갱신에는 $O(logN)$이 걸립니다.
앞서 이야기한 누적합으로 계산을 한다면, 구간합 계산에는 $O(1)$이 걸리고, 값 갱신에는 $O(N)$이 걸립니다.
갱신이 없는 경우라면, 메모리측면에서도 속도측면에서도 세그먼트트리보다 누적합이 더 적합합니다.

작성방법

세그먼트 트리를 구성하고 사용하기 위해서는 보통 3가지 함수를 만들어 사용하게 됩니다.

init 함수

세그먼트트리의 초기형태를 구성합니다

update 함수

값을 갱신합니다

query 함수

구간값을 반환합니다

init 함수

세그먼트는 배열 또는 벡터에 값을 저장합니다.
해당하는 구조의 크기를 정해주어야합니다.
배열의 크기를 정확히 계산하면, $2^{\lceil log_2N\rceil +1}$ 입니다.
이를 시프트연산을 적용하여 계산하면 다음과 같이 작성할 수 있습니다.

seg.resize(2 << (int)ceil(log2(N)));

메모리에 여유가 있고, 쉽게 작성하고 싶다면 그냥 4배로 해도 됩니다.
세그먼트트리가 요구하는 크기는 $4N$을 넘지 않습니다.

seg.resize(N << 2);

크기를 지정해주었다면, init 함수를 실행시키면 됩니다.

init 함수는 다음과 같습니다.

void init(int node, int s, int e) {
    if(s == e) seg[node] = v[s];
    else {
        int m = (s + e) / 2;
        init(2 * node, s, m);
        init(2 * node + 1, m + 1, e);
        seg[node] = seg[2 * node] + seg[2 * node + 1];
    }
}

이분탐색과 유사한 방식으로 구간을 재귀적으로 분할합니다.
배열을 이진트리로 활용하여, 좌측자식 노드는 $2\times node$ 이고, 우측 자식노드는 $2\times node+1$ 입니다.
init함수를 실행할 때, node는 1이고, s는 0이며, e는 N-1입니다.

update 함수

값을 변경해주는 update함수도 init함수와 유사합니다.

void update(int node, int s, int e, int idx, int val) {
    if(idx < s || e < idx) return;
    if(s == e) seg[node] = val;
    else {
        int m = (s + e) / 2;
        update(2 * node, s, m, idx, val);
        update(2 * node + 1, m + 1, e, idx, val);
        seg[node] = seg[2 * node] + seg[2 * node + 1];
    }
}

update함수를 실행할 때, node는 1이고, s는 0이며, e는 N-1입니다.
idx는 변경해줄 값의 인덱스를 의미하며, val은 변경값을 의미합니다.

query 함수

query함수를 통해 구간값을 가져올 수 있습니다.

int query(int node, int s, int e, int left, int right) {
    if(right < s || e < left) return 0;
    if(left <= s && e <= right) return seg[node];
    int m = (s + e) / 2;
    return query(2 * node, s, m, left, right)
        + query(2 * node + 1, m + 1, e, left, right);
}

query함수를 실행할 때, node는 1이고, s는 0이며, e는 N-1입니다.
left와 right는 포함구간을 의미합니다.

요약코드

세그먼트트리를 실용적으로 빠르게 사용할 수 있는 코드입니다.

int seg_size = 0;
vector<long long> seg, seg_;
void init_(int n, int s, int e) {
    if(s == e) {seg_[n] = seg[s]; return;}
    int a = n << 1, b = a + 1, m = (s + e) >> 1, k = m + 1;
    init_(a, s, m), init_(b, k, e);
    seg_[n] = seg_[a] + seg_[b];
}
void update_(int n, int s, int e, int i, long long d) {
    if(i < s || e < i) return;
    if(s == e) {seg_[n] = d; return;}
    int a = n << 1, b = a + 1, m = (s + e) >> 1, k = m + 1;
    update_(a, s, m, i, d), update_(b, k, e, i, d);
    seg_[n] = seg_[a] + seg_[b];
}
long long query_(int n, int s, int e, int l, int r) {
    if(r < s || e < l) return 0;
    if(l <= s && e <= r) return seg_[n];
    int a = n << 1, b = a + 1, m = (s + e) >> 1, k = m + 1;
    long long A = query_(a, s, m, l, r), B = query_(b, k, e, l, r);
    return A + B;
}
void init() {
    seg_size = seg.size();
    int z = 2 << (int)ceil(log2(seg_size));
    seg_.resize(z);
    init_(1, 0, seg_size - 1);
}
void update(int i, long long d) {
    seg[i] = d;
    update_(1, 0, seg_size - 1, i, d);
}
long long query(int l, int r) {
    return query_(1, 0, seg_size - 1, l, r);
}

레이지

앞서 본 세그먼트 트리는 한번에 하나의 값을 변경했습니다.
그러나 특정구간의 값을 한번에 바꾸게 된다면 효율성이 떨어지게 됩니다.
그런 경우에 사용할 수 있는 것이 Lazy-Propagation 입니다.
레이지세그는 구간의 값을 갱신할 때, 바로 값을 반영하지 않고, 레이지 배열에 담아둡니다.
그리고 해당 구간의 값을 확인해야 하는 경우에만 몰아서 업데이트를 해줍니다.
기존 세그먼트 트리에서 M개의 값을 변경한다면 $O(MlogN)$이 걸리게 되지만, 이러한 방식으로 몰아서 갱신한다면 $O(logN)$ 시간만에 가능합니다.
기존 init, update, query 외에도 propagate함수가 필요하고, 각 함수가 조금씩 변경되지만 큰 변화는 없습니다.

int seg_size = 0;
vector<long long> seg, seg_, lazy_;
void prop_calc(int n, int s, int e, long long x) {
    int a = n << 1, b = a + 1;
    seg_[n] += x * (e-s+1);
    if(s != e) lazy_[a] += x, lazy_[b] += x;
}
long long seg_calc(long long A, long long B) {
    return A + B;
}
void propagate_(int n, int s, int e) {
    if(!lazy_[n]) return;
    int a = n << 1, b = a + 1;
    prop_calc(n, s, e, lazy_[n]);
    lazy_[n] = 0;
}
void init_(int n, int s, int e) {
    if(s == e) {seg_[n] = seg[s]; return;}
    int a = n << 1, b = a + 1, m = (s + e) >> 1, k = m + 1;
    init_(a, s, m), init_(b, k, e);
    seg_[n] = seg_calc(seg_[a], seg_[b]);
}
void update_(int n, int s, int e, int l, int r, long long d) {
    propagate_(n, s, e);
    if(r < s || e < l) return;
    int a = n << 1, b = a + 1, m = (s + e) >> 1, k = m + 1;
    if(l <= s && e <= r) {prop_calc(n, s, e, d); return;}
    update_(a, s, m, l, r, d), update_(b, k, e, l, r, d);
    seg_[n] = seg_calc(seg_[a], seg_[b]);
}
long long query_(int n, int s, int e, int l, int r) {
    propagate_(n, s, e);
    if(r < s || e < l) return 0;
    if(l <= s && e <= r) return seg_[n];
    int a = n << 1, b = a + 1, m = (s + e) >> 1, k = m + 1;
    return seg_calc(query_(a, s, m, l, r), query_(b, k, e, l, r));
}
void init() {
    seg_size = seg.size();
    int z = 2 << (int)ceil(log2(seg_size));
    seg_.resize(z), lazy_.resize(z);
    init_(1, 0, seg_size - 1);
}
void update(int l, int r, long long d) {
    update_(1, 0, seg_size - 1, l, r, d);
}
long long query(int l, int r) {
    return query_(1, 0, seg_size - 1, l, r);
}

문제 추천

백준 12844 - XOR
xor 특성과 함께 세그먼트를 변형하여 사용하는 기본 문제

백준 7578 - 공장
2022 SCPC 2차예선 2번 - 반협동게임 에서도 나왔던 교차확인 문제

백준 1168 - 요세푸스 문제 2
쿼리를 변형하여 해당 순서를 가져오는 문제