노드의 개수가 5인 BIT를 구현해보던 중,
규칙이 성립하기 어려움을 보았다.
둘 중에 어느 그림이 맞는지 몰라 두번 그려보고 결국 그래프의 모습으로 나타내 보았다.
먼저의 이진법으로 인덱스를 표시한 그림을 보면
앞서 배운 업데이트와 구간합을 구할때 마지막 1의 비트를 변환하는 방법은 통용되지 않음을 알 수 있다.
그래서 노드의 개수를 넘는 가장작은 2의 제곱수의 길이에 해당 그래프는 포함시키는 방법으로 해결했다.
이 경우 공간의 낭비가 심한 것 같다. 다른 방법이 있을까?
'알고리즘' 카테고리의 다른 글
| EOF ( End Of File ) 과 while문 (0) | 2022.01.11 |
|---|---|
| BOJ2439 - 별찍기 (0) | 2022.01.11 |
| 바이너리 인덱스 트리 ( Binary Index Tree, BIT ) (0) | 2022.01.03 |
| 벨만 포드 알고리즘 ( BellmanFord Algorithm ) (0) | 2021.12.31 |
| 기타 알고리즘 ( 투 포인터, 구간 합 ) (0) | 2021.12.31 |
