반응형 [C++로 배우는 알고리즘과 자료구조 심화] Day 3: 펜윅 트리 (Fenwick Tree, Binary Indexed Tree) 펜윅 트리 (Fenwick Tree, Binary Indexed Tree)펜윅 트리(BIT, Fenwick Tree)는 배열의 구간 합을 효율적으로 계산하고 업데이트할 수 있는 자료구조입니다. 세그먼트 트리와 유사하지만, 구현이 더 간단하고 메모리 사용량이 적습니다.펜윅 트리의 주요 특징시간 복잡도:업데이트: (O(\log n))쿼리: (O(\log n))구현 방법:트리의 각 노드는 배열의 특정 구간에 대한 정보를 저장합니다.이진수의 비트 연산을 활용하여 구간을 관리합니다.펜윅 트리의 기본 연산업데이트 (Update): 특정 인덱스의 값을 업데이트합니다.쿼리 (Query): 특정 인덱스까지의 구간 합을 계산합니다.펜윅 트리의 구현다음은 C++로 펜윅 트리를 구현한 예제입니다. 구간 합을 구하고 구간 값을.. 2024. 8. 1. 이전 1 다음 반응형
