세그먼트 트리 (구간 트리), 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

사실 어려운 알고리즘 중에서 세그먼트 트리만 제대로 쓸 줄 안 다면 정말 정말 편하다.

세그 문제가 아닌데도 세그로 풀리는 문제가 많기 때문이다.

세그먼트 트리만 깊게 파서 나쁠건 없다고 생각한다.

공부 대비 가성비가 정말 좋은 알고리즘 이다.

세그먼트 트리의 구조

세그먼트 트리는 간단하게 부모의 노드가 자손의 노드들 중 리프 노드를 관리한다고 생각하면 된다.

만약 입력값이 1부터 6까지 주어졌다고 생각해보자.

세그먼트 트리의 모양은 아래와 같다.

노드1 : 인덱스 1부터 6까지 관리하는 노드

노드2 : 인덱스 1부터 3까지 관리하는 노드

노드3 : 인덱스 4부터 6까지 관리하는 노드

노드4 : 인덱스 1부터 2까지 관리하는 노드

노드5 : 인덱스 3부터 3까지 관리하는 노드

 

이렇게 구간을 절반씩 나눠서 관리하는 부모 노드들이 존재한다.

만약 구간합을 관리하는 트리라면 각 노드는 노드들이 관리하는 구간의 합이 저장되어 있다.

최소값을 관리하는 노드라면 관리하는 구간의 최소값이 저장되어 있다.

세그먼트 트리 예제

2042번: 구간 합 구하기

세그먼트 트리의 쿼리

시간복잡도 : O(logN)

인덱스	1	2	3	4	5	6
값	1	2	3	4	5	6

인덱스 3부터 5까지 구간합을 질의하는 쿼리를 처리하는 방법을 알아보자.

위의 표와 트리 그림 참고

• 탐색은 최상위 노드부터 깊이 탐색으로 시작한다.
• 최상위 노드인 노드1의 구간을 확인한다.
• 노드1은 인덱스 3부터 5까지 구간을 포함하지만 포함되지는 않으므로 자식 노드를 확인해야 한다.
• 이제 노드2의 구간과 노드3의 구간을 확인한다.
• 노드2의 구간은 인덱스 1부터 3이고 노드3의 구간은 인덱스 4부터 6이다.
• 노드2와 노드3도 노드1과같은 이유로 자식노드를 확인해야 한다.
• 이제 노드4~노드7을 확인해보자.
• 노드4의 구간은 인덱스 1부터 2이고 인덱스 3부터 5까지 구간을 불포함하므로 더 이상 확인할 필요가 없다.
• 노드5의 구간은 인덱스 3이고 인덱스 3부터 5까지 구간에 포함되므로 노드5를 선택한다.
• 노드6의 구간은 인덱스 4부터 5이고 인덱스 3부터 5까지 구간에 포함되므로 노드6을 선택한다.
• 노드7의 구간은 인덱스 6이고 인덱스 3부터 5까지 구간을 불포함하므로 더 이상 확인할 필요가 없다.
• 이렇게 선택된 노드5와 노드6은 각 각 저장된 값을 리턴해서 최종적으로 합쳐지게 된다.
• 따라서 답은 3(노드 5)+9(노드 6) = 12로 정해진다.

// 구간합 세그먼트 트리에서 구간합 질의를 구하는 쿼리
// 노드가 관리하는 입력값 인덱스 : s ~ e
// 구간 질의 : l ~ r
ll query(int node, int s, int e, int l, int r) {
    // 질의 구간이 노드 구간을 벗어났다면 확인할 필요가 없음
    if (r < s || e < l) return 0;
    
    // 질의 구간이 노드 구간에 포함된다면 노드 구간합을 반환
    if (l <= s && e <= r) return seg[node];
    
    // 질의 구간이 노드 구간과 겹친다면 자식 노드로 일을 넘겨준다.
    int mid = (s + e) / 2;
    return query(node*2, s, mid, l, r) + query(node*2+1, mid+1, e, l, r);
}

세그먼트 트리의 초기값 설정

시간 복잡도 : O(NlogN)

구간합을 저장하는 세그먼트 트리의 초기값 설정하는 방법을 알아보자.

세그먼트 트리의 저장은 배열을 사용하는데 저장은 인덱스 1부터 사용한다.

왼쪽 자식 : 부모 노드 x 2

오른쪽 자식 : 부모 노드 x 2 + 1

부모 : 자식 / 2

• 최상위 노드인 1번 노드부터 탐색을 시작한다.
• 현재 확인하고 있는 노드의 구간의 길이가 1이라면 그 구간의 값을 노드에 저장한다.
• 1이 아니라면 구간을 반으로 나눠서 왼쪽 자식 노드와 오른쪽 자식 노드를 재귀로 초기값을 설정해 준다.
• 두 개의 자식 노드의 합을 현재 확인하고 있는 노드에 저장한다.
• 그 값을 부모 노드로 리턴한다.

이렇게 재귀로 초기값을 설정해 주면 된다.

// 구간합 세그먼트 트리에서 입력값이 주어졌을 때 초기값 설정
// 노드가 관리하는 입력값 인덱스 : s ~ e
ll init(int node, int s, int e) {

    // 구간의 길이가 1일 때
    // 구간합은 입력값 그대로이기 때문에 바로 저장하고 반환
    if (s==e) {
        seg[node] = an[s];
        return seg[node];
    }
    
    // 구간의 길이가 1이 아닐 때
    // 구간합은 자식 노드의 합이기 때문에
    // 자식노드를 먼저 초기화 시켜준 후 각 각 더해서 초기화
    int mid = (s + e) / 2;
    seg[node] = init(node*2, s, mid) + init(node*2+1, mid+1, e);
    return seg[node];
}

세그먼트 트리의 원소 한 개 업데이트

시간 복잡도 : O(logN)

세그먼트 트리의 쿼리와 같은 방식으로 하면 된다.

다만 노드의 값을 리턴하기 전에 원하는 값으로 갱신한다.

부모 노드는 세그먼트 트리의 초기값 설정처럼 다시 업데이트해주면 된다.

// 구간합 세그먼트 트리에서의 갱신
// 노드가 관리하는 입력값 인덱스 : s ~ e
// 갱신하고 싶은 입력값 인덱스 : x
// 갱신할 값 : y
ll update(int node, int s, int e, int x, ll y) {
    // 갱신하고 싶은 인덱스가 노드구간에 포함되지 않는다면 노드의 값 반환
    if (x < s || e < x) return seg[node];
    
    // 갱신하고 싶은 인덱스를 찾았을 경우 노드의 값 갱신
    if (s == e) return seg[node] = y;
    
    // 갱신하고 싶은 인덱스가 노드구간에 포함
    // 하지만 노드구간 길이가 1이 아닐경우 자식에게 일을 넘겨줌
    // 자식중에서 값이 갱신되므로 현재 노드의 값도 갱신후 반환
    int mid = (s + e) / 2;
    return seg[node] = update(node*2, s, mid, x, y) + update(node*2+1, mid+1, e, x, y);
}

예제 전체 코드

#include <bits/stdc++.h>
using ll=long long;
using namespace std;

ll seg[4000010], an[1000010]; // 세그먼트 트리, 입력값

// 구간합 세그먼트 트리에서 입력값이 주어졌을 때 초기값 설정
// 노드가 관리하는 입력값 인덱스 : s ~ e
ll init(int node, int s, int e) {

    // 구간의 길이가 1일 때
    // 구간합은 입력값 그대로이기 때문에 바로 저장하고 반환
    if (s==e) {
        seg[node] = an[s];
        return seg[node];
    }
    
    // 구간의 길이가 1이 아닐 때
    // 구간합은 자식 노드의 합이기 때문에
    // 자식노드를 먼저 초기화 시켜준 후 각 각 더해서 초기화
    int mid = (s + e) / 2;
    seg[node] = init(node*2, s, mid) + init(node*2+1, mid+1, e);
    return seg[node];
}

// 구간합 세그먼트 트리에서 구간합 질의를 구하는 쿼리
// 노드가 관리하는 입력값 인덱스 : s ~ e
// 구간 질의 : l ~ r
ll query(int node, int s, int e, int l, int r) {
    // 질의 구간이 노드 구간을 벗어났다면 확인할 필요가 없음
    if (r < s || e < l) return 0;
    
    // 질의 구간이 노드 구간에 포함된다면 노드 구간합을 반환
    if (l <= s && e <= r) return seg[node];
    
    // 질의 구간이 노드 구간과 겹친다면 자식 노드로 일을 넘겨준다.
    int mid = (s + e) / 2;
    return query(node*2, s, mid, l, r) + query(node*2+1, mid+1, e, l, r);
}

// 구간합 세그먼트 트리에서의 갱신
// 노드가 관리하는 입력값 인덱스 : s ~ e
// 갱신하고 싶은 입력값 인덱스 : x
// 갱신할 값 : y
ll update(int node, int s, int e, int x, ll y) {
    // 갱신하고 싶은 인덱스가 노드구간에 포함되지 않는다면 노드의 값 반환
    if (x < s || e < x) return seg[node];
    
    // 갱신하고 싶은 인덱스를 찾았을 경우 노드의 값 갱신
    if (s == e) return seg[node] = y;
    
    // 갱신하고 싶은 인덱스가 노드구간에 포함
    // 하지만 노드구간 길이가 1이 아닐경우 자식에게 일을 넘겨줌
    // 자식중에서 값이 갱신되므로 현재 노드의 값도 갱신후 반환
    int mid = (s + e) / 2;
    return seg[node] = update(node*2, s, mid, x, y) + update(node*2+1, mid+1, e, x, y);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m, k;
    cin >> n >> m >> k;

    for (int i=1; i<=n; i++) {
        cin >> an[i];
    }

    init(1, 1, n);

    for (int i=0; i<m+k; i++) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        if (a==1) {
            update(1, 1, n, b, c);
        }
        else if (a==2) {
            cout << query(1, 1, n, b, c) << '\n';
        }
    }
    return 0;
}

세그먼트 트리의 시간 복잡도

전처리 시간복잡도가 O(NlogN)이다.

쿼리 또는 갱신 시간 복잡도가 O(logN) 이므로 쿼리의 개수를 Q라 하면 시간 복잡도는 O(QlogN)이다.

하지만 구간 갱신은 시간 복잡도가 O(NlogN) 이므로 시간 복잡도는 O(NQlogN)이다.

구간 업데이트도 O(logN) 만에 하는 방법이 존재하는데 느리게 갱신되는 세그먼트 트리를 사용하면 된다.

느리게 갱신되는 세그먼트 트리

기존 방식의 세그먼트 트리에서의 문제점은 구간 업데이트 시 시간 복잡도가 O(NlogN)이라는 것이다.

이 문제점을 해결하기 위해 원소(인덱스)를 구간 업데이트 시 그 구간을 관리하는 최상위 노드에게 일을 던져주면 된다.

나중에 그 노드를 참조할 때 그때 일을 처리해준 후 자식에게 남은 일을 넘기는 방식이다.

예를 들어 위 그림에서 인덱스 1~인덱스 3까지 10을 각 각 더해주는 연산을 한다고 가정해보자.

기존의 방식은 노드 1부터 깊이 탐색으로 인덱스를 업데이트해주고 부모 노드로 올라가면서 업데이트하는 방식이다.

반면에 Lazy 방식은 어차피 인덱스1~인덱스3이 각 각 10씩 증가가 되면 노드2는 30이 증가될 것임을 알기 때문에

노드2에다가 관리하는 원소들이 10씩 증가된다는 것을 저장한다.

나중에 노드2가 참조가 되면 그때 노드2의 값을 30 증가시켜주고 자식에게 각 각 다시 10을 저장하는 방식이다.

기존에 저장한 값이 있다면 누적된다.

이렇게 되면 구간합을 구할 때처럼 구간 업데이트 똑같이 시간 복잡도가 O(NlogN) 이 된다.

 

느리게 갱신되는 세그먼트 트리 예제

10999번: 구간 합 구하기 2

느리게 갱신되는 세그먼트 트리의 전파

// node의 구간 s~e
void lazy_update(int node, int s, int e) {
    // 만약 처리해야 할 일이 있다면
    if(lazy[node]) {
        // 관리하는 구간의 개수만큼 미리 계산해서 증가시켜준다
        seg[node] += (e-s+1)*lazy[node];
        
        // 리프노드가 아닐경우 자식에가 일을 전파한다.
        if (s!=e) {
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        
        // 처리가 끝났다면 초기화
        // 여기에서는 0이 일이 없다는 뜻이므로 0으로 초기화
        lazy[node] = 0;
    }
}

느리게 갱신되는 세그먼트 트리의 업데이트

// s,e  : node가 관리하는 구간 s~e
// l,r  : 업데이트 해야할 구간 l~r
// diff : 업데이트시 더해줘야할 값 diff
ll update(int node, int s, int e, int l, int r, ll diff) {
    // 노드를 확인하기전에 전파해야할 값이 있다면 처리
    lazy_update(node, s, e);
    
    if (r < s || e < l) return seg[node];
    
    // 노드 구간이 업데이트 구간에 포함된다면(업데이트를 해야할 구간에 도달했다면)
    if (l <= s && e <= r) {
        // 전파해야할 일을 추가해준다.
        lazy[node] += diff;
        
        // 전파 처리
        lazy_update(node, s, e);
        
        // 전파가 완료되었으면 더이상 자식노드로 가지않고 리턴
        // 자식의 업데이트는 나중에 자식이 참조될 때 처리하게 될 예정
        // 자식이 참조되지 않는다면 영원히 자식은 업데이트 되지 않는다.
        return seg[node];
    }
    
    
    int mid = (s + e) / 2;
    return seg[node] = update(node*2, s, mid, l, r, diff) + update(node*2+1, mid+1, e, l, r, diff);
}

느리게 갱신되는 세그먼트 트리의 쿼리

// s, e : node가 관리하는 구간 s~e
// l, r : 쿼리를 처리해야 할 구간 l~r
ll query(int node, int s, int e, int l, int r) {
    // 전파가 남아있다면 전파 처리
    lazy_update(node, s, e);
    
    // 이 후 코드는 세그먼트 트리와 똑같다.
    if (r < s || e < l) return 0;
    if (l <= s && e <= r) return seg[node];
    int mid = (s + e) / 2;
    return query(node*2, s, mid, l, r) + query(node*2+1, mid+1, e, l, r);
}

예제 전체 코드

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

ll seg[4000010], lazy[4000010], an[1000010];

// node의 구간 s~e
void lazy_update(int node, int s, int e) {
    // 만약 처리해야 할 일이 있다면
    if(lazy[node]) {
        // 관리하는 구간의 개수만큼 미리 계산해서 증가시켜준다
        seg[node] += (e-s+1)*lazy[node];
        
        // 리프노드가 아닐경우 자식에가 일을 전파한다.
        if (s!=e) {
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        
        // 처리가 끝났다면 초기화
        // 여기에서는 0이 일이 없다는 뜻이므로 0으로 초기화
        lazy[node] = 0;
    }
}

ll init(int node, int s, int e) {
    if (s==e) return seg[node] = an[s];
    int mid = (s + e) / 2;
    seg[node] = init(node*2, s, mid) + init(node*2+1, mid+1, e);
    return seg[node];
}

// s, e : node가 관리하는 구간 s~e
// l, r : 쿼리를 처리해야 할 구간 l~r
ll query(int node, int s, int e, int l, int r) {
    // 전파가 남아있다면 전파 처리
    lazy_update(node, s, e);
    
    // 이 후 코드는 세그먼트 트리와 똑같다.
    if (r < s || e < l) return 0;
    if (l <= s && e <= r) return seg[node];
    int mid = (s + e) / 2;
    return query(node*2, s, mid, l, r) + query(node*2+1, mid+1, e, l, r);
}

// s,e  : node가 관리하는 구간 s~e
// l,r  : 업데이트 해야할 구간 l~r
// diff : 업데이트시 더해줘야할 값 diff
ll update(int node, int s, int e, int l, int r, ll diff) {
    // 노드를 확인하기전에 전파해야할 값이 있다면 처리
    lazy_update(node, s, e);
    
    if (r < s || e < l) return seg[node];
    
    // 노드 구간이 업데이트 구간에 포함된다면(업데이트를 해야할 구간에 도달했다면)
    if (l <= s && e <= r) {
        // 전파해야할 일을 추가해준다.
        lazy[node] += diff;
        
        // 전파 처리
        lazy_update(node, s, e);
        
        // 전파가 완료되었으면 더이상 자식노드로 가지않고 리턴
        // 자식의 업데이트는 나중에 자식이 참조될 때 처리하게 될 예정
        // 자식이 참조되지 않는다면 영원히 자식은 업데이트 되지 않는다.
        return seg[node];
    }
    
    
    int mid = (s + e) / 2;
    return seg[node] = update(node*2, s, mid, l, r, diff) + update(node*2+1, mid+1, e, l, r, diff);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m, k;
    cin >> n >> m >> k;

    for (int i=1; i<=n; i++) {
        cin >> an[i];
    }

    init(1, 1, n);

    for (int i=0; i<m+k; i++) {
        int a;
        cin >> a;
        if (a==1) {
            int b, c;
            ll d;
            cin >> b >> c >> d;
            update(1, 1, n, b, c, d);
        }
        else if (a==2) {
            int b, c;
            cin >> b >> c;
            cout << query(1, 1, n, b, c) << '\n';
        }
    }
    return 0;
}

세그먼트 트리, 느리게 갱신되는 세그먼트 트리의 사용

구간 업데이트가 필요하다면 느리게 갱신되는 세그먼트 트리를 사용하고

구간 업데이트가 필요없고 구간 쿼리만 필요하다면 세그먼트 트리를 사용하면 된다.

무조건 느리게 갱신되는 세그먼트 트리만 사용해도 세그먼트 트리를 포함하기 때문에 가능하다.