Bit

펜윅트리 (Fenwick Tree, Binary Indexed Tree, BIT)펜윅트리는 트리 구조를 1차원 배열로 구현한 자료구조로, 각 위치에서 특정 구간을 대표하는 값을 저장하여 빠르게 구간 합 등을 계산할 수 있다. 업데이트와 쿼리 연산의 시간 복잡도는 O(logN)이다. 1기반 인덱싱을 사용하기 때문에 배열의 크기를 N + 1 (N은 데이터의 크기)로 설정하는 경우가 많다. 세그먼트 트리보다 상대적으로 구현이 간단하고 메모리 사용량이 적다.  주요 연산 비교연산펜윅 트리세그먼트 트리구간 쿼리O(logN)O(logN)단일 업데이트O(logN)O(logN)구간 업데이트O(NlogN)O(logN) (Lazy Propagation 사용 시)메모리 사용량O(N)O(4 * N) 펜윅 트리 코드#inclu..