티스토리 뷰
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 |
공유하기 링크
댓글
공지사항
- Total
- 415,092
- Today
- 5
- Yesterday
- 70
링크
TAG
- 소녀시대
- 써니
- 태그를 입력해 주세요.
- girls generation
- sudoku
- Avisynth
- 테티이
- 크로스파이어
- AVS
- TAKE LTE
- 테이크LTE
- cs4
- Sunny
- solver
- 자작
- Logo
- 가사
- 풀이
- SNSD
- 소시
- 풀기
- Filter
- 알고리즘
- 인코딩
- 수도쿠
- C++
- png
- 라데온
- 다운
- 유리