지연 전파 세그먼트 트리의 갱신 불변식

구간 덧셈을 현재 합에 즉시 반영하고 자식 전파만 미루는 과정을 예제로 추적하며 대입·덧셈 태그 합성 순서를 설명합니다.

알고리즘 · 원리·구현·운영

지연 전파 세그먼트 트리는 각 노드가 담당 구간의 답을 즉시 유지하되, 그 변경을 자식 표현에 내려 쓰는 시점만 늦추는 자료구조입니다. 따라서 핵심은 “태그가 있는가”보다 부모 합·자식 합·pending 태그가 서로 어떤 불변식을 만족하는지 추적하는 데 있습니다.

기본 모델을 식으로 쓰면 노드 구간 길이가 len일 때 구간 전체에 d를 더하는 apply는 sum += len*d를 즉시 수행하고 lazyAdd += d를 남깁니다. 이후 부분 연산이 그 노드를 통과할 때만 태그를 자식에 복사하므로, 갱신 시점과 표현 전파 시점을 구분할 수 있습니다.

구간 갱신과 전체 리프 방문 비용

배열의 구간 전체에 값을 더하고 구간 합을 반복 조회한다고 합시다. 길이가 큰 구간마다 원소를 모두 바꾸면 갱신 하나가 O(n)입니다. 세그먼트 트리는 구간을 절반씩 나누어 합을 저장합니다. 갱신이 노드 구간 전체를 덮으면 현재 합을 바로 바꾸고, 자식에게 전달할 변경만 나중으로 미룰 수 있습니다.

이것이 지연 전파(lazy propagation)입니다. “아직 아무것도 하지 않았다”가 아니라 현재 노드의 합에는 반영했고 자식의 표현에만 아직 남아 있다는 뜻입니다.

반열린 구간과 노드 저장 값

배열 [1,2,3,4]의 루트는 [0,4), 자식은 [0,2)와 [2,4)입니다. 각 노드는 sum과 아직 자식에 전달하지 않은 lazyAdd를 가집니다.

합은 먼저 바꾸고 자식 전파만 미룹니다 화살표는 부모에서 자식으로 전달할 변경입니다. 전체에 3을 더한 뒤 루트 합은 22지만 자식 합은 3과 7에 머물며, 아래로 내려갈 때 +3을 전파합니다.

그림을 글로 읽기

[0,4) · sum=22: 원래 합 10 + 4×3 · lazyAdd=3
[0,2) · sum=3: 아직 부모의 +3 미반영
[2,4) · sum=7: 아직 부모의 +3 미반영

[0,4) · sum=22 → [0,2) · sum=3: 내려갈 때 +3
[0,4) · sum=22 → [2,4) · sum=7: 내려갈 때 +3

전체 합을 조회하면 루트의 22를 바로 반환합니다. 자식까지 읽을 필요가 없습니다. [1,3)처럼 일부만 조회하면 부모의 pending 변경을 자식 합과 태그에 먼저 전달해야 합니다.

구간 갱신과 부분 조회 추적

연산	논리 배열	루트 합	핵심 동작
초기화	[1,2,3,4]	10	하위 합으로 구성
[0,4)에 +3	[4,5,6,7]	22	루트만 합+12, 태그+3
[1,3) 합 조회	그대로	22	자식 전파 후 5+6=11
[2,4)에 +2	[4,5,8,9]	26	오른쪽 합+4, 상위 합 재계산

태그를 달기만 하고 루트 합을 10으로 두면 두 번째 행 직후 전체 조회가 틀립니다. 반대로 태그를 자식에게 보낸 뒤 부모 태그를 0으로 비우지 않으면 다음 하강 때 같은 변경을 두 번 적용합니다.

덧셈만 지원하는 슈도코드

각 노드 구간 [l,r)는 비어 있지 않고 트리는 미리 구성되어 있다고 가정합니다. 외부 API는 0<=ql<=qr<=n을 검증하고 빈 구간은 갱신 무시·합 0으로 처리합니다.

apply(node,l,r,d):
    sum[node] += (r-l)*d
    lazyAdd[node] += d

push(node,l,r):
    if r-l == 1 or lazyAdd[node] == 0: return
    mid = l + (r-l)//2
    apply(left(node), l, mid, lazyAdd[node])
    apply(right(node), mid, r, lazyAdd[node])
    lazyAdd[node] = 0

add(node,l,r,ql,qr,d):
    if qr<=l or r<=ql: return
    if ql<=l and r<=qr:
        apply(node,l,r,d)
        return
    push(node,l,r)
    mid = l + (r-l)//2
    add(left(node),l,mid,ql,qr,d)
    add(right(node),mid,r,ql,qr,d)
    sum[node] = sum[left(node)] + sum[right(node)]

query(node,l,r,ql,qr):
    if qr<=l or r<=ql: return 0
    if ql<=l and r<=qr: return sum[node]
    push(node,l,r)
    mid = l + (r-l)//2
    return query(left(node),l,mid,ql,qr) +
           query(right(node),mid,r,ql,qr)

부분 갱신 뒤에는 두 자식 합으로 부모를 다시 계산합니다. push 직후 이미 부모 합은 자식 합과 일치하므로 조회가 값을 바꾸는 논리 연산은 아니지만, 구현상 태그·자식 배열은 바뀔 수 있습니다. 따라서 query를 읽기 전용 함수라고 보고 동시 실행해도 된다고 단정하면 안 됩니다.

대입·덧셈 태그의 합성 순서

노드 전체에 +3이 걸린 뒤 =5가 오면 자식에 내려갈 최종 값은 5이고, 반대로 =5 뒤 +3이 오면 최종 값은 8입니다. 그러므로 pending tag를 단순한 숫자의 합으로 저장할 수 없습니다. (hasSet,setValue,addValue)는 “대입이 있으면 그 값으로 바꾼 뒤 add를 적용한다”는 순서를 저장합니다. 예를 들어 set(5) 뒤 add(3)은 setValue=5, addValue=3으로 표현되고, 새로운 set이 오면 이전 add는 자식에 전달할 태그에서 버려집니다.

새 연산	기존 pending 태그에 할 일	현재 합 갱신
set(x)	hasSet=true, setValue=x, addValue=0	length×x
add(d)	addValue+=d	sum+=length×d
자식으로 push	set을 먼저, add를 나중에 적용	자식 apply 함수가 합도 갱신

set(0)은 유효한 갱신이므로 0을 “대입 없음”의 sentinel로 쓰면 안 됩니다. 이 표는 위 덧셈 전용 코드의 확장 규칙이며, 대입 API를 구현하려면 apply·push 모두 이 표현으로 바꾸어야 합니다.

시간 복잡도와 수치 범위

고정 배열의 트리 구성은 O(n), 저장은 O(n), 구간 합·구간 덧셈은 일반적으로 O(log n)입니다. 각 단계에서 완전히 덮인 구간은 멈추고 경계 경로만 더 내려가기 때문입니다. “태그를 미루니 모든 갱신이 O(1)”은 아닙니다.

length*d, 누적 태그, 자식 합이 모두 표현 가능한 타입이어야 합니다. 일부 노드만 바꾼 뒤 overflow 오류로 빠져나오면 구조가 깨지므로 충분한 타입·입력 한도 또는 안전한 변경 방식이 필요합니다. 빈 배열은 트리를 만들지 않고 별도 처리합니다.

작은 기준 배열 [1,2,3,4]에서 전체 +3, [1,3) 조회, [2,4)+2를 실행하면 각각 전체 합 22, 부분 합 11, 최종 전체 합 26이 예상됩니다. set(5) 뒤 add(3)를 같은 구간에 넣었을 때는 해당 원소가 8, add(3) 뒤 set(5)일 때는 5여야 하므로 태그 합성 순서를 별도 assertion으로 고정합니다.

기준 배열과 겹친 구간 갱신의 비교

작은 배열에서 전체·부분·한 원소·빈 구간을 번갈아 갱신하고 모든 구간 합을 직접 합산과 비교합니다. 같은 구간에 덧셈을 두 번, 대입 뒤 덧셈, 덧셈 뒤 0 대입을 넣어 순서 차이를 확인합니다.

특히 전체 갱신 직후 전체 조회와, 그 뒤 좁은 조회를 모두 검사해야 합니다. 전자는 현재 합 갱신 누락을, 후자는 push 누락·중복 전파를 찾습니다. 지연 전파는 계산을 없애는 것이 아니라 저장 표현 사이의 반영 시점을 관리하는 기법입니다.

후속·관련 개념

함께 읽을 문서

전체 기술 지식

선택 연습 · 관련 질문 1개

질문은 이해를 확인하는 보조 자료입니다. 학습 경로와 문서의 범위는 질문 수와 독립적입니다.

구간 전체에 값을 더하고 구간 합을 조회합니다. segment tree의 lazy propagation은 무엇을 미루나요?