요약
- Segment Tree의 발전된 형태로, 부분합을 빠르게 계산하여 구간 합을 O(log n)에 구하는 자료구조
- 배열 인덱스의 이진법 표현(LSB)을 활용
본문
-
구간 합(또는 누적 합) 문제를 효율적으로 해결하는 데 사용
-
누적합을 저장해두면 특정 구간의 구간합을 두 위치를 빼줌으로써 상수 시간안에 구할 수 있음
-
배열 인덱스의 이진법 표현을 활용한 자료구조
-
LSB (Least Significant Bit): 이진수 표현에서 가장 낮은 자리의 비트를 의미함
-
각 노드가 특정 범위의 구간합을 나타내도록 설계됨
- 인덱스에서 마지막으로 세트된 비트가 해당 인덱스가 담당하는 구간의 길이
-
끝나는 구간 다음으로 더해야하는 구간을 이진수 표현으로 찾음
-
구간 트리의 궁극적인 진화 형태
-
구간 합 대신 부분합을 빠르게 계산 가능한 자료구조
psum[i] = A[0] + ... + A[i]
- 하나의 긴 구간 밑에 작은 구간이 2개 있을때, 두 구간중 오른쪽은 항상 지워도 됨 => n개의 숫자로 표현 가능함
tree[i] => 오른쪽 끝 위치가 A[i]인 구간합
구간합 계산 방식
A[i]까지의 구간합 psum[i]를 계산하고 싶으면 i에서 끝나는 구간합 tree[pos]에 답을 더함
pos에서 끝나는 구간 다음으로 더해야하는 구간을 어떻게 찾을까?
- 이진수 표현을 통해 문제를 해결 할 수 있음
- 인덱스를 i를 이진수로 바꾸고 바꾼 이진수의 오른쪽 끝에서 연속된 0의 개수가 구간의 길이를 정함
마지막 비트를 추출 하기 위해
pos & -pos
-pos: pos의 보수 이기때문에
보수는 모든 비트를 반전 시킨 후, +1 해주는 개념
- 이 둘 사이의 and 연산이므로 num의 마지막 비트 LSB를 찾아줌