TwentyTwentyOne

세그먼트 트리, 펜윅 트리, 스파스 테이블 비교: 상황별 자료구조 선택 전략데이터 구간 연산을 빠르게 처리하기 위해 가장 많이 사용되는 자료구조는 세그먼트 트리(Segment Tree),펜윅 트리(Fenwick Tree/BIT), 그리고 **스파스 테이블(Sparse Table)**입니다.이번 글에서는 이 세 가지 자료구조의 구조적 특징, 시간 복잡도, 사용 상황을 비교하여실전 문제에서 올바르게 선택할 수 있는 전략을 정리합니다.✅ 자료구조 개요 비교자료구조 연산 종류 초기화 시간 쿼리 시간 업데이트 시간세그먼트 트리합, 최댓값, 최솟값 등O(N)O(log N)O(log N)펜윅 트리합, XOR 등 누적합O(N)O(log N)O(log N)스파스 테이블최댓값, 최솟값, GCDO(N log N)O(1)❌ ..

Lazy Propagation + 모노이드 세그먼트 트리: 다양한 쿼리와 구간 업데이트를 동시에 처리하는 고급 기법지금까지 우리는세그먼트 트리를 통해 빠른 구간 쿼리를Lazy Propagation을 통해 효율적인 구간 업데이트를**모노이드(Monoid)**를 통해 다양한 연산으로의 확장을각각 배웠습니다.이번 글에서는 이 세 가지를 하나의 프레임워크로 통합하여**“다양한 연산을 지원하는 구간 갱신 + 쿼리용 세그먼트 트리”**를 구현하고 실전 문제에 바로 활용할 수 있도록 정리합니다.✅ 목표: 어떤 연산도 지원하는 세그먼트 트리 만들기기능 지원 여부구간 쿼리✅구간 갱신 (덧셈, 대입 등)✅연산 유형 (합, 최대, 최소, GCD 등)✅✅ 설계 전략: 모노이드 + 지연 전파 (Lazy Propagation)기..

Lazy Propagation 완벽 이해: 세그먼트 트리에서 구간 업데이트를 효율적으로 처리하는 방법세그먼트 트리에서 구간 단위로 값을 업데이트해야 할 경우, 단순하게 처리하면 **시간복잡도가 O(N)**이 되어버려 효율이 급격히 떨어집니다.이를 해결하는 고급 기법이 바로 **Lazy Propagation(지연 전파)**입니다.이번 글에서는 Lazy Propagation의 개념, 필요성, 작동 방식, Python 코드 구현, 실전 문제 적용까지 단계별로 정리합니다.✅ Lazy Propagation이란?세그먼트 트리에서 여러 구간을 한 번에 갱신할 때, 갱신 정보를 지연시켜 저장해 두었다가**필요할 때만 적용(전파)**하는 최적화 기법입니다.📉 왜 필요한가?기존 세그먼트 트리로 아래와 같은 연산을 수행한..

세그먼트 트리(Segment Tree) 완벽 정리: 기본 개념부터 구간 합, 최솟값, Lazy Propagation까지**세그먼트 트리(Segment Tree)**는 배열의 구간 정보를 효율적으로 저장하고, 빠르게 질의/갱신할 수 있는 자료구조입니다.특히 구간 합, 최댓값, 최솟값, 특정 조건 카운트 등에서 **O(log N)**의 시간복잡도를 제공하여,코딩 테스트, 실전 알고리즘 문제에서 매우 중요한 역할을 합니다.이번 글에서는 세그먼트 트리의 구조, 구축(Build), 쿼리(Query), 업데이트(Update) 방법과**Lazy Propagation(지연 업데이트)**까지 단계별로 정리합니다.✅ 세그먼트 트리란?원래 배열을 트리 형태로 분할하여 저장하는 구조각 노드는 특정 구간을 대표하고, 구간 전체..