- 마지막 비트 크기로 현재 인덱스의 ‘저장 개수’ 계산
i & -i
-
int tree[sum_size]; int sum(int i){ int res = 0; while (i > 0){ res += tree[i]; i -= (i & -i); } return res; } void update(int i, int dif){ // update값이 dif // 기존 값과의 dif를 점진적 비트 크기로 이동하면서 업데이트 while (i < sum_size){ tree[i] += dif; i += (i & -i); } } int getSection(int start, int end){ return sum(end) - sum(start - 1); }
- psum과의 차이는?
- psum은 일차원 배열
- fenwick tree는 배열이지만 가상적 트리 구조
- 빈번한 업데이트에 따른 구간 합
- 펜윅트리, 세그먼트 트리가 유리
- 업데이트 없고, 구간합만 필요
- psum만 사용해도 충분