-
펜윅트리Algorithm/세그먼트, 펜윅트리 2020. 3. 5. 01:56123456789101112131415161718192021222324252627282930313233343536//펜윅 트리의 완전한 구현//펜윅 트리의 구현, 가상의 배열 A[]의 부분 합을//빠르게 구현할 수 있도록 한다. 초기화시에는 A[]의//원소가 전부 0이라고 생각한다struct FenwickTree{vector<int> tree;FenwickTree(int n) : tree(n+1) {}//A[0...pos]의 부분 합을 구한다.int sum(int pos){//인덱스가 1부터 시작한다고 생각하자.++pos;int ret = 0;while(pos > 0){ret += tree[pos];//다음 구간을 찾기 위해 최종 비트를 지운다.pos &= (pos-1);}return ret;}//A[pos]에 val을 더한다void add(int pos, int val){//인덱스가 1부터 시작한다고 생각하자.++pos;while(pos < tree.size()){tree[pos] += val;pos += (pos & -pos);}}};
cs 펜윅트리
부분 합을 이용해 구간 합을 구하는 트리
박스 안의 숫자는 index이고, 밑의 조그만 숫자는 해당 index를 2진수로 표현한 것입니다.
tree[i] : 위 그림에서 index가 i인 부분의 합
가상의 A[] 배열의 구간합 [0...pos]를 구하기 위해선
pos + 1 의 index를 가지는 박스를 찾은다음, pos + 1의 최종 비트를 계속지워 나가며 구해지는 박스들을 모두 더하면 됩니다.(pos + 1은 1번부터 시작하기 때문입니다.)
펜윅트리를 갱신하기 위해선
pos + 1 의 index를 가지는 박스를 찾은다음, pos + 1의 최종비트를 계속 더해 만나는 박스들에 새로운 값을 갱신해 주면 됩니다.
시간복잡도
sum : O(lgn)
add : O(lgn)
종만북2
'Algorithm > 세그먼트, 펜윅트리' 카테고리의 다른 글
Segment with Lazy Propagation (0) 2020.04.06 Segment Tree (0) 2020.03.13