전체 글26 지연 갱신 가이드: 세그먼트 트리 구간 업데이트 $O(\log N)$ 기법 💻 지연 갱신벌써 20년 가까이 코딩만 하고 있는 시니어 개발자 형이야. 오늘은 너희가 꼭 알아야 할 기초를 담백하게 풀어줄게. 실무 노하우까지 꽉꽉 눌러 담았으니 천천히 따라와 봐.데이터 구조의 정점에 서 있는 세그먼트 트리(Segment Tree)는 배열의 구간 합, 최솟값, 최댓값 같은 걸 $O(\log N)$의 시간 복잡도 내에 처리할 수 있는 아주 강력한 도구야. 그런데 일반적인 세그먼트 트리는 단일 원소 바꾸는 건 잘하지만, 특정 구간 전체를 한꺼번에 바꾸는 구간 업데이트(Range Update)를 하면 성능이 $O(N \log N)$으로 훅 떨어지는 한계가 있어. 이런 병목 현상을 해결하려고 나온 기술이 바로 지연 갱신(Lazy Propagation)이야. 업데이트 연산을 필요할 때까지 미.. 2026. 4. 7. 세그먼트 트리 가이드: 구간 합 쿼리 $O(\log N)$ 최적화 💻 세그먼트 트리벌써 20년 가까이 코딩만 하고 있는 시니어 개발자 형이야. 오늘은 너희가 꼭 알아야 할 기초를 담백하게 풀어줄게. 실무 노하우까지 꽉꽉 눌러 담았으니 천천히 따라와 봐.현대 데이터 처리 환경에서 엄청나게 많은 배열 데이터를 효율적으로 관리하는 건 시스템 성능의 핵심이야. 특히 데이터가 실시간으로 변하는 동적 환경에서 특정 구간의 합(Range Sum)을 구하는 작업은 정말 자주 생기거든. 그냥 배열을 쓰면 단순 합산은 $O(N)$이나 걸리고, 누적 합 기법은 업데이트할 때마다 $O(N)$의 비용이 들어서 고민이 깊어지지. 이런 딜레마를 해결하려고 만든 게 바로 세그먼트 트리(Segment Tree)야. 이 자료구조는 이진트리의 특성을 써서 데이터 업데이트랑 구간 쿼리 모두를 $O(\l.. 2026. 4. 7. 이전 1 2 3 4 5 다음
