이동식 저장소

펜윅 트리를 모른다면 다음 글을 참고하자. 펜윅 트리 (바이너리 인덱스 트리) 블로그: 세그먼트 트리 (Segment Tree) 에서 풀어본 문제를 Fenwick Tree를 이용해서 풀어보겠습니다. Fenwick Tree는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다. Fenwick Tree를 구현하려면, 어떤 수 X www.acmicpc.net 기본적인 펜윅 트리는 점 업데이트, 구간 쿼리를 각각 로그 시간에 수행할 수 있다. 하나의 수를 로그 시간에 업데이트하고, 구간의 합을 로그 시간에 구할 수 있다는 뜻이다. 반대로 구간 업데이트와 점 쿼리도 각각 로그 시간에 수행할 수 있다. 어떻게요? 수열 $A$에 대해 구간 업데이트와 점 쿼리를 수행해야 한다고 가정하자. 수열 $..