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

lazy propagation은 완전히 덮인 구간의 변경을 하위 노드에 즉시 모두 전파하지 않고 지연 표시로 보관하는 방식입니다. 현재 노드의 집계는 올바르게 갱신하고 더 내려갈 때 필요한 변경을 전달해야 합니다.

동작 원리와 전제

길이 n인 구간에 d를 더하면 합은 n*d만큼 증가합니다. lazy 값을 붙였다는 이유로 집계 갱신을 생략하면 전체 구간 조회가 틀립니다. 부분 조회·갱신 전에 pending 변경을 자식에 전달하는 불변식을 유지합니다.

선택과 실패 처리

구간 대입과 덧셈을 함께 지원하면 변경의 합성 순서가 중요합니다. add 후 set과 set 후 add는 결과가 다르므로 tag를 단순히 더할 수 없습니다. 반열린·닫힌 구간 규칙과 overflow를 명확히 합니다.

구체적인 사례와 검증

구간 길이 4에 3을 더하면 sum은 12 늘어나고 자식에게 전달할 add tag가 누적됩니다. 전체 구간 조회는 자식으로 내려가지 않아도 현재 sum을 반환할 수 있어야 합니다. 그 뒤 절반 구간에 대입이 들어오면 기존 tag를 필요한 자식에 반영하거나 합성 규칙에 맞게 처리합니다. lazy tag는 '아직 아무것도 안 했다'가 아니라 상위 집계에는 반영됐고 하위 표현에 남은 변경을 뜻합니다. 연산 순서를 바꾼 무작위 테스트로 이 불변식을 확인하고 sentinel 값과 실제 0 대입을 혼동하지 않도록 tag 존재 상태를 별도로 표현합니다.

겹친 갱신·전체·부분 범위·한 원소·대입과 덧셈 순서를 기준 배열과 무작위 비교합니다. lazy는 계산을 없애는 것이 아니라 필요한 시점까지 미루어 전체 연산 비용을 줄이는 기법입니다.