Coding Interview Prep · 강의

구간 갱신을 위한 지연 전파

전체 구간에 대한 갱신을 미룹니다

레슨 4/413개 단계

구간 갱신을 위한 지연 전파은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

구간 갱신 문제

질의에서 l부터 r까지 모든 원소에 5를 더하라고 한다면 어떨까요? 각 리프를 건드리면 갱신마다 O(n)이 걸리므로 많은 구간 갱신을 처리하기에는 너무 느립니다. 😰

지연 처리 아이디어

지연 전파를 사용하면 노드가 아직 자식에게 전달하지 않은 변경 사항을 기억할 수 있습니다. 실제로 자식이 필요해질 때까지 작업을 미룰 수 있습니다.

보류 중인 작업을 위한 두 번째 배열

트리와 함께 지연 배열을 유지합니다. 지연 배열은 해당 노드의 전체 구간에 적용되지만 아직 아래로 전달되지 않은 갱신을 저장합니다.

lazy = [0] * (4 * n)

노드 전체에 적용하기

갱신 범위가 노드 전체를 포함하면 저장된 값을 조정하고 변경 사항을 지연 배열에 쌓은 다음 멈춥니다. 아래로 내려갈 필요가 없습니다.

seg[node] += (r - l + 1) * val
lazy[node] += val

아래로 내려가기 전에 전달하기

자식을 방문하기 전에 보류 중인 지연 값을 두 자식 모두에게 아래로 전달하십시오. 그러면 자식을 읽는 순간 자식의 값이 정확하게 유지됩니다.

def push_down(node, l, r):
    if lazy[node]:
        apply(2*node, l, mid)
        apply(2*node+1, mid+1, r)
        lazy[node] = 0

노드마다 있는 세 가지 경우

각 노드에서 질의 구간은 서로 겹치지 않거나, 완전히 포함되거나, 부분적으로 겹칩니다. 각각 건너뛰거나, 지연 처리하거나, 두 절반으로 재귀 호출합니다.

지연 갱신도 로그 시간

전체가 포함된 노드는 일찍 멈추므로 구간 갱신은 O(log n)개의 노드만 방문합니다. 이것이 지연 처리를 사용하는 가장 큰 이점입니다. ⚡

질의도 아래로 전파

구간 질의도 재귀 호출 전에 아래로 전파해야 최신 자식 값을 읽을 수 있습니다. 이를 잊는 것이 지연 전파에서 흔히 발생하는 버그입니다.

재귀 후 위로 취합

자식을 갱신한 뒤에는 자식 값으로 부모를 다시 계산해야 합니다. 이렇게 위로 취합하면 모든 내부 정점이 자신의 하위 트리와 일관된 상태를 유지합니다.

seg[node] = seg[2*node] + seg[2*node+1]

대입과 덧셈의 차이

지연 전파는 여러 연산에 적용할 수 있지만, 대입과 덧셈은 결합 방식이 다릅니다. 구현하기 전에 대기 중인 두 갱신을 어떻게 합칠지 결정해야 합니다.

지연 전파가 필요한 경우

정말 구간 갱신이 필요할 때만 지연 전파를 사용하십시오. 점 갱신만 필요하다면 일반 세그먼트 트리만으로 더 간단하게 충분히 해결할 수 있습니다.

빠른 확인

정점의 자식으로 재귀 호출하기 전에 무엇을 해야 합니까?

인터랙티브 레슨에서 답해보세요

복습: 지연 갱신

지연 전파를 배웠습니다. 대기 중인 변경 사항을 저장하고, 아래로 내려가기 전에 전파하며, 내려간 뒤 위로 취합하면 O(log n)에 구간 갱신을 수행할 수 있습니다. 🎉

무료로 시작

AI 튜터와 함께 Coding Interview Prep을(를) 배우세요 — 무료

브라우저에서 실제 코드를 작성하고 실행하며, 24/7 AI 튜터로부터 즉각적인 도움을 받고, 웹이나 앱에서 중단한 부분부터 계속 학습하세요.

코스: 90
레슨: 360

무료로 학습 시작 전체 코스 보기

자주 묻는 질문

“구간 갱신을 위한 지연 전파” 강의는 무료인가요?

네 — “구간 갱신을 위한 지연 전파” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

“구간 갱신을 위한 지연 전파”에서 뭘 배우나요?

전체 구간에 대한 갱신을 미룹니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.

“구간 갱신을 위한 지연 전파” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

← Coding Interview Prep(으)로 돌아가기