바이너리 인덱스 트리: 구현과 활용
바이너리 인덱스 트리
1. 점 업데이트와 구간 합 查询
lowbit 함수
바이너리 인덱스 트리의 핵심은 lowbit 연산입니다:
lowbit(x) = x & (-x)
이 연산은 x의 이진 표현에서 가장 오른쪽에 있는 1의 위치 값을 반환합니다.
예를 들어, x = (0010010011000)₂ 라면:
-x = ~x + 1 = (1101101101000)₂
x & (-x) = (0000000001000)₂
동작 원리
배열 a[1...n]이 ...
7월 10일 04:24에 게시됨