Binary Indexed Tree(Fenwick tree ; 펜윅트리)
LSB 본격적인 Binary Indexed Tree를 설명하기에 앞서 LSB(k)에 대해 간단히 알아보자. (나중에 쓰이는 연산임!) 어떤 수 k를 2진수로 바꿨을 때 가장 첫 번째로 1이 등장하는 위치를 d라 하자. LSB(k) = 2^d 를 말한다. 아래의 예시를 보면 이해에 도움이 될 것이다. LSB(10) 10 = 1010(2진수) 가장 첫 번째로 1이 등장하는 위치 d = 1 (오른쪽부터 0으로 카운트 시작) LSB(10) = 2^1 = 2 LSB(12) 12 = 1100 d = 2 LSB(12) = 2^2 = 4 LSB(8) 8 = 1000 d = 3 LSB(8) = 2^3 = 8 LSB 빠르게 구하기 실제 코드에서 LSB(k)를 상수시간 내 계산하는 방법은 -k(2의 보수)를 활용하는 것이다..
트리 자료구조 정의 부모- 자식 관계를 계층적으로 표현한 보다 일반적인 자료구조 용어 정리 부모(조상)노드, 자식(자손)노드 루트노드 : 모든 노드의 조상노드 리프노드 : 자식이 없는 노드 레벨(level) : 루트 노드 "0레벨" 부터 시작하여 한 세대씩 내려가며 1씩 증가 깊이(depth) : 루트에서 다른 노드를 연결하는 에지 개수 높이(height) : 노드의 높이는 자식 노드까지의 가장 큰 깊이 트리 높이 : 루트 노드의 높이 경로 : 두 노드 사이를 연결하는 엣지의 시퀀스. 경로의 길이는 에지의 수 분지수(degree) : 노드의 분지수는 자신의 자식 노드 수. 트리의 분지수는 가장 큰 분지수로 정의 부트리(subtree) : 어떤 노드와 그 노드의 자손노드들로 구성된 부분 트리 이진트리 모든..