세그먼트 트리, 펜윅 트리, 스파스 테이블 비교: 상황별 자료구조 선택 전략

세그먼트 트리, 펜윅 트리, 스파스 테이블 비교: 상황별 자료구조 선택 전략데이터 구간 연산을 빠르게 처리하기 위해 가장 많이 사용되는 자료구조는 세그먼트 트리(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)❌ ..
Programming 2025. 5. 7. 15:59
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/05   »
일 월 화 수 목 금 토
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
글 보관함
반응형