Fenwick Tree

GitHub - hijkl2e/problem_solving: 알고리즘 문제 해결

요약

Fenwick Tree는 구간 질의를 O(logM)에 수행할 수 있는 자료 구조이다.

Segment Tree보다 상수가 작으나 수행 가능한 연산이 일부 제한된다.

 

Fenwick Tree의 기본 연산은 PURQ이다.

Point Update와 Range Query 모두 비트 연산으로 O(logM)에 수행할 수 있다.

추가적으로 select 연산도 O(logM)에 가능하다.

 

PURQ Fenwick Tree를 응용하면 RUPQ 및 RURQ 연산도 O(logM)에 수행할 수 있다.

RUPQ의 경우 Range Update를 2번의 Point Update로 처리하는 것이 핵심이다.

RURQ의 경우 PURQ Fenwick Tree와 RUPQ Fenwick Tree를 동시에 관리해준다.

대략적으로 설명하자면 RUPQ가 구간 초기값을 그리고 PURQ가 구간 보정값을 담당한다.

 

연습 문제

1. Supercomputer

PURQ

2. Just for Sidekicks

vector<FT<>>

3. Movie Collection

N = R + M

4. Cookie Selection

좌표 압축 + select

 

끝

끝