-
이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다.
바이너리 인덱스 트리 (BIT, Binary Indexed Tree)
데이터 업데이트가 가능한 상황에서의 구간 합 (Interval Sum)
어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고
그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고,
3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다.
그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면12가 될 것이다.
바이너리 인덱스 트리 사용
2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결할 수 있는 자료구조를 의미.
== 펜윅 트리(fenwick tree) 라고도 함.
0이 아닌 마지막 비트를 찾는 방법
특정한 숫자 K의 0이 아닌 마지막 비트를 찾기 위해서 K & -K를 계산하면 된다.n=8 for i in range (n+1): print(i, "의 마지막 비트:", (i & -i))
하면 일치하게 됨.
바이너리 인덱스 트리 :
> 트리 구조 만들기 : 0이 아닌 마지막 비트 = 내가 저장하고 있는 값들의 개수
> 업데이트 : 0이 아닌 마지막 비트만큼 더하면서 구간들의 값을 변경 (예시 = 3rd)
최악의 경우를 가정하여도 시간 복잡도는 logN 을 보장함.
> 누적 합 구하기 : 0이 아닌 마지막 비트만큼 빼면서 구간들의 값의 합 계산 (예시 = 11th)
최악의 경우도 logN의 시간 복잡도를 보장함.'개발 > 이코테' 카테고리의 다른 글
REST의 등장 배경, 구성요소, REST API 정의, REST API연습 사이트 JSON 정의 (0) 2022.04.24 벨만 포드 알고리즘 정의, 예제, 구현 방식 (0) 2022.04.24 최소 공통 조상 (Lowest Common Ancestor) 정의, 원리 (0) 2022.04.24 이진 탐색 트리 정의, 동작 방법, 트리의 순회 (전위, 중위, 후위) (0) 2022.04.22 우선 순위 큐 정의, 구현 방법, 완전 이진 트리 (0) 2022.04.22 댓글 (비로그인 댓글 허용하지 않습니다.)