[자료구조] 느리게 갱신되는 세그먼트 트리 (재귀·비재귀) + Rust 구현

소리·2025년 9월 9일

이 글은 세그먼트 트리에서 이어집니다.
기본 세그먼트 트리에 관한 내용은 위 링크를 참고해 주세요.

안녕하세요! 소리입니다 👋
이번 글에서는 지연 전파를 이용해 더욱 강력한 기능을 가지는 느리게 갱신되는 세그먼트 트리(Lazy Propagation Segment Tree)에 대한 내용을 준비했어요.

🚀 느리게 갱신되는 세그먼트 트리란?

일반적인 세그먼트 트리는 데이터를 하나만 갱신할 수 있었어요.
값의 변경은 리프 노드까지 이루어져야 하기 때문에, 기존 방법으로 구간 전체를 갱신하려면 아무리 빨라도 $O(N)$ 의 시간이 걸려요.
이 방법은 구간을 업데이트하기에는 너무나 오래 걸리는 시간이죠.

따라서 세그먼트 트리가 범위 업데이트를 지원하도록 하려면 새로운 방법이 필요해요.

지연 전파

리프 노드까지 바로 업데이트하지 않고, 필요할 때만 업데이트하는 아이디어는 어떨까요?

구간 업데이트 요청이 들어왔을 때 부모 노드에 요청이 있었다는 Lazy 태그를 남긴 후, 실제 값이 필요해질 때 부모 노드에서 아래로 새로운 값을 내려 연산을 실행하는 방법을 사용하면 시간을 크게 아낄 수 있어요.

	일반 세그먼트 트리	느리게 갱신되는 세그먼트 트리
구간 갱신	$O(N)$	$O(logN)$
구간 쿼리 계산	$O(logN)$	$O(logN)$

갱신 단계의 동작

자세한 구현을 알아볼게요.
느린 전파 동작을 크게 세 단계로 나눌 수 있어요.

Lazy 전파
업데이트가 필요한 노드까지 내려가는 도중 상위에 존재하는 Lazy 태그를 아래로 내려줘요.
노드 갱신
갱신이 필요한 노드에 Lazy 태그를 붙이고, 노드의 값을 갱신해요.
상위 노드 업데이트
갱신된 노드의 값을 이용해 상위 노드의 값을 업데이트해요.

쿼리 단계의 동작

지연 전파 기법을 사용하면 쿼리 단계의 동작도 살짝 수정해야 해요.
기본 세그먼트 트리에서의 동작과 같지만, 쿼리의 결과를 구하기 전에 Lazy 전파를 해주어야 해요.

Lazy 전파
갱신 단계와 마찬가지로, 쿼리를 구하기 위해 필요한 노드까지 내려가는 도중 상위에 존재하는 Lazy 태그를 아래로 내려줘요.
쿼리 구하기
이 과정은 기본 세그먼트의 동작과 같아요.

🧑‍💻 지연 전파 구현하기

$N=100,000$ 인 구간 합을 구할 수 있는 느리게 갱신되는 세그먼트 트리를 구현해볼게요.
세그먼트 트리의 생성과 구성은 일반적인 세그먼트 트리와 같아요.

다만, 트리에 Lazy 태그를 적용할 수 있도록 노드의 구조체를 따로 만들었어요.

struct Node {
    value: i32,
    lazy: i32,
}

일반적인 구현

구간 데이터 갱신하기

fn update(segtree: &mut [Node], left: usize, right: usize, val: i32) {

    // 재귀용 함수 (left·right: 요청한 범위, start·end: 현재 노드의 담당 범위)
    fn update_recursive(segtree: &mut [Node], left: usize, right: usize, idx: usize, start: usize, end: usize, val: i32, lazy: i32) {

        // Lazy 전파
        segtree[idx].value += lazy * (end - start + 1) as i32;
        segtree[idx].lazy += lazy;

        // 구간에 속하는 경우
        if left <= start && end <= right {
            segtree[idx].value += val * (end - start + 1) as i32;
            segtree[idx].lazy += val;
        }
        // 일부만 겹치는 경우
        else if start <= right && left <= end {
            let mid = (start + end + 1) >> 1;

            // 재귀로 자녀 노드 확인
            update_recursive(segtree, left, right, idx << 1, start, mid - 1, val, segtree[idx].lazy);
            update_recursive(segtree, left, right, idx << 1 | 1, mid, end, val, segtree[idx].lazy);

            // 전파된 Lazy 제거
            segtree[idx].value = segtree[idx << 1].value + segtree[idx << 1 | 1].value;
            segtree[idx].lazy = 0;
        }
    }

    // 루트 노드(1번 노드)에서부터 노드 확인
    update_recursive(segtree, left, right, 1, 0, (1 << 17) - 1, val, 0)
}

구간 쿼리 코드 수정하기

일반적인 세그먼트 트리 코드와 유사하지만, Lazy 태그 처리 부분이 추가됐어요.

fn query(segtree: &mut [Node], left: usize, right: usize) -> i32 {

    // 재귀용 함수 (left·right: 요청한 범위, start·end: 현재 노드의 담당 범위)
    fn query_recursive(segtree: &mut [Node], left: usize, right: usize, idx: usize, start: usize, end: usize, lazy: i32) -> i32 {

        // Lazy 전파
        segtree[idx].value += lazy * (end - start + 1) as i32;
        segtree[idx].lazy += lazy;

        // 구간에 속하는 경우
        if left <= start && end <= right {
            segtree[idx].value
        }
        // 일부만 겹치는 경우
        else if start <= right && left <= end {
            let mid = (start + end + 1) >> 1;

            // 재귀로 자녀 노드 확인
            let a = query_recursive(segtree, left, right, idx << 1, start, mid - 1, segtree[idx].lazy);
            let b = query_recursive(segtree, left, right, idx << 1 | 1, mid, end, segtree[idx].lazy);
            
            // 전파된 Lazy 제거
            segtree[idx].lazy = 0;

            a + b
        }
        // 전혀 겹치지 않는 경우
        else {
            // 덧셈의 항등원
            0
        }
    }

    // 루트 노드(1번 노드)에서부터 노드 확인
    query_recursive(segtree, left, right, 1, 0, (1 << 17) - 1, 0)
}

비재귀로 구현하기

느리게 갱신되는 세그먼트 트리도 비재귀 구현이 가능해요.

구간 데이터 갱신하기

위 사진에서 초록색 구간을 갱신한다면, 파란색 구간의 Lazy 태그가 전파되어야 해요.
파란색 구간을 어떻게 재귀 없이 접근할 수 있을까요?

파란색 구간을 순회하는 방법은 초록색 구간 순회 과정과 유사해요.
파란색 구간은 범위 양 끝 리프 노드의 상위 노드에 속하기 때문이에요.

왼쪽 끝의 리프 노드를 시작점으로 두고, 상위로 올라가 볼게요.
파란색 노드는 시작 노드를 오른쪽 하위 노드로 두는 노드와 그 상위 노드들이에요.
마찬가지로 오른쪽 끝의 리프 노드를 왼쪽 하위 노드로 두는 노드와 그 상위 노드들도 파란색 노드예요.

💡 파란색 노드 여부 확인하기

리프 노드의 인덱스를 idx라고 하고 살펴볼게요.

idx의 i번째 위의 조상이 부모의 왼쪽 자녀 노드라면, idx >> i의 값은 짝수일 거에요.
따라서 idx >> i << i == idx이라면 idx의 부모 노드부터 i번째 위의 조상은 모두 idx 노드를 오른쪽 하위 노드로 둔 적이 없는 노드예요.

idx $=20$ 일때,

idx $\gg2=5$ 이고, idx $\gg2\ll2=20=$ idx

idx $\gg3=2$ 이고, idx $\gg3\ll3=16\neq$ idx

따라서 파란색 노드는 아래 수식을 만족하는지로 판별할 수 있어요.
(left >> i << i != left)
((right + 1) >> i << i != right + 1)

fn update(segtree: &mut [Node], left: usize, right: usize, val: i32) {
    let left = left | 1 << 17;
    let right = right | 1 << 17;
    
    // 상위 노드의 lazy 태그 전파 (위에서부터 내려오며 순회)
    for i in (1..=17).rev() {
        if left >> i << i != left {
            let p = left >> i;
            segtree[p << 1].value += segtree[p].lazy * (1 << (i - 1));
            segtree[p << 1].lazy += segtree[p].lazy;
            segtree[p << 1 | 1].value += segtree[p].lazy * (1 << (i - 1));
            segtree[p << 1 | 1].lazy += segtree[p].lazy;
            segtree[p].lazy = 0;
        }
        if (right + 1) >> i << i != right + 1 {
            let p = right >> i;
            segtree[p << 1].value += segtree[p].lazy * (1 << (i - 1));
            segtree[p << 1].lazy += segtree[p].lazy;
            segtree[p << 1 | 1].value += segtree[p].lazy * (1 << (i - 1));
            segtree[p << 1 | 1].lazy += segtree[p].lazy;
            segtree[p].lazy = 0;
        }
    }

    // 구간 갱신 진행
    let mut dl = left;
    let mut dr = right;
    let mut size = 1;
    while dl <= dr {
        if dl & 1 == 1 {
            segtree[dl].value += val * size;
            segtree[dl].lazy += val;
            dl += 1;
        }
        if dr & 1 == 0 {
            segtree[dr].value += val * size;
            segtree[dr].lazy += val;
            dr -= 1;
        }
        dl >>= 1;
        dr >>= 1;
        size <<= 1;
    }

	// 상위 노드 업데이트 (아래에서부터 올라가며 순회)
    for i in 1..=17 {
        if left >> i << i != left {
            let p = left >> i;
            segtree[p].value = segtree[p << 1].value + segtree[p << 1 | 1].value;
        }
        if (right + 1) >> i << i != right + 1 {
            let p = right >> i;
            segtree[p].value = segtree[p << 1].value + segtree[p << 1 | 1].value;
        }
    }
}

구간 쿼리 구하기

상위 노드의 Lazy 태그 전파 과정은 구간 데이터 갱신 과정과 같아요.

fn query(segtree: &mut [Node], left: usize, right: usize) -> i32 {
    let mut left = left | 1 << 17;
    let mut right = right | 1 << 17;

    // 상위 노드의 lazy 태그 전파 (위에서부터 내려오며 순회)
    for i in (1..=17).rev() {
        if left >> i << i != left {
            let p = left >> i;
            segtree[p << 1].value += segtree[p].lazy * (1 << (i - 1));
            segtree[p << 1].lazy += segtree[p].lazy;
            segtree[p << 1 | 1].value += segtree[p].lazy * (1 << (i - 1));
            segtree[p << 1 | 1].lazy += segtree[p].lazy;
            segtree[p].lazy = 0;
        }
        if (right + 1) >> i << i != right + 1 {
            let p = right >> i;
            segtree[p << 1].value += segtree[p].lazy * (1 << (i - 1));
            segtree[p << 1].lazy += segtree[p].lazy;
            segtree[p << 1 | 1].value += segtree[p].lazy * (1 << (i - 1));
            segtree[p << 1 | 1].lazy += segtree[p].lazy;
            segtree[p].lazy = 0;
        }
    }

    // 쿼리 구하기
    let mut res = 0;
    while left <= right {
        if left & 1 == 1 {
            res += segtree[left].value;
            left += 1;
        }
        if right & 1 == 0 {
            res += segtree[right].value;
            right -= 1;
        }
        left >>= 1;
        right >>= 1;
    }
    res
}