펜윅 트리
펜윅 트리은 배열의 누적 집계와 단일 위치 갱신을 이진수 인덱스 패턴으로 처리한다 구간 합 자료구조 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다...
| 분류 | 자료구조 · 구간 합 자료구조 |
|---|---|
| 목적 | 배열의 누적 집계와 단일 위치 갱신을 이진수 인덱스 패턴으로 처리한다 |
| 처리 방식 | 각 인덱스 i에서 i&(-i)를 이용해 담당하는 구간 크기를 구하고, 접두사 합 질의에서는 인덱스의 최하위 1비트를 제거하며 더한다 |
| 복잡도·성능 | 점 갱신·접두사 합 O(log n), 공간 O(n) |
| 필수 조건 | 결합 가능한 연산과 접두사 집계 구조가 필요하며 일반적인 범위 최소·최대에는 제약이 있다 |
| 참고 문헌 | 기술 참고 자료 |
| 관련 분야 | 알고리즘, 자료구조 |
펜윅 트리은 배열의 누적 집계와 단일 위치 갱신을 이진수 인덱스 패턴으로 처리한다 구간 합 자료구조 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다.[1]
처리 과정은 각 인덱스 i에서 i&(-i)를 이용해 담당하는 구간 크기를 구하고, 접두사 합 질의에서는 인덱스의 최하위 1비트를 제거하며 더한다. 갱신은 반대 방향으로 영향을 받는 항목을 바꾼다. 실제 구현에서는 각 단계의 결과가 어떤 의미를 갖는지 불변식을 정하고, 입력·갱신·질의의 처리 경로를 구분한다.
성능은 점 갱신·접두사 합 O(log n), 공간 O(n) 올바르게 적용하려면 결합 가능한 연산과 접두사 집계 구조가 필요하며 일반적인 범위 최소·최대에는 제약이 있다 데이터의 범위와 해시·비교·수치 처리 규칙, 실패 시의 동작 등을 명확히 해야 구현체에 따라 결과가 달라지는 상황을 줄일 수 있다.
활용 및 관련 기법과 비교하면 누적 빈도·역전쌍·온라인 구간 합에 사용한다. 세그먼트 트리보다 구현·메모리가 단순한 경우가 많다. 성능 평가에서는 초기 자료구조 구성과 질의·갱신, 저장 공간을 분리하여 분석하고, 실제 하드웨어의 캐시 및 메모리 접근 비용도 함께 고려한다.[2]