[C++] 펜윅트리 (이진 인덱스 트리) - 구간합 구해주는 트리

struct FenwickTree {

   vector<int> tree;

   FenwickTree(int n) : tree(n + 1) {}

   inline int sum(int pos) {

       ++pos;

       int ret = 0;

       while (pos > 0) {

          ret += tree[pos];

          pos &= (pos - 1);

       }

       return ret;

   }

   inline void add(int pos, int val) {

       ++pos;

       while (pos < (int) tree.size()) {

          tree[pos] += val;

          pos += (pos & -pos);

       }

   }

};

사용법

생성자 FenwickTree fenwickTree(n) : n은 들어갈 노드의 개수

int sum(int pos) : 0번~pos번째까지의 합을 구해준다.(내부적으로 1~pos+1로 동작)

void add(int pos, int val) : pos번째 노드에 val을 더해준다.

성능

합이랑 더하기 시간복잡도 모두 O(lgN)

응용

5~8번 노드의 구간합은 fenwickTree.sum(8) - fenwickTree.sum(5-1)

저작자표시비영리변경금지

• 카카오스토리
• 트위터
• 페이스북

'프로그래밍/알고리즘 > C++' 카테고리의 다른 글

[C++ STL] 동적 2차원 배열 사용법(vector)  (3)	2015.08.24
[C++] 구간트리 (Binary Indexed Tree) - 구간 최대,최소값  (1)	2015.08.12
[C++] 펜윅트리 (이진 인덱스 트리) - 구간합 구해주는 트리  (0)	2015.07.28
[C++] 비트 마스크 배열 (큰 비트 마스크)  (0)	2015.07.27
트리 최적 노드 삽입 순서  (0)	2015.07.09
버블 정렬 알고리즘 오름차순  (0)	2015.07.08