배열의 값이 자주 바뀌고 구간 합도 반복 조회합니다. prefix sum과 Fenwick tree는 어떻게 선택하나요?

정적 prefix sum은 구간 합을 빠르게 구하지만 한 값 변경이 뒤 누적값 전체를 바꿀 수 있습니다. Fenwick tree는 일부 구간 합을 저장해 점 갱신과 prefix 조회를 로그 시간으로 처리하는 절충입니다.

동작 원리와 전제

구간 합은 prefix(r)-prefix(l-1)로 구할 수 있고 Fenwick의 인덱스 최하위 비트를 이용해 관련 노드를 이동합니다. 보통 1-based 인덱스를 사용하므로 0 입력과 범위 경계를 명확히 합니다. 합의 타입 overflow도 확인합니다.

선택과 실패 처리

값이 거의 안 바뀌면 단순 prefix 배열이 더 읽기 쉽고 빠를 수 있습니다. 범위 갱신·최솟값·복잡한 연산은 Fenwick의 적용 조건과 segment tree 같은 대안을 비교합니다. 모든 결합 연산을 합처럼 역연산할 수 있는 것은 아닙니다.

구체적인 사례와 검증

점 값 5를 8로 바꿀 때 Fenwick에는 새 값 8을 더하는 것이 아니라 차이 3을 반영해야 하는 인터페이스가 일반적입니다. 원래 값을 저장하지 않으면 갱신 의미를 잘못 적용할 수 있습니다. prefix 조회 범위가 포함인지 제외인지와 사용자 배열의 0-based 인덱스 변환을 한 함수에서 관리합니다. 누적 합으로 가중 추출 위치를 찾는다면 모든 가중치가 비음수라는 단조성 조건도 필요합니다. 같은 tree 구조를 쓴다고 음수 값의 prefix에서 이진 탐색이 항상 가능하지는 않습니다. 연산별 전제와 불변식을 작은 기준 배열로 검사하겠습니다.

빈 범위·첫·끝 원소·음수·반복 갱신을 선형 기준 구현과 대조합니다. 시간 복잡도뿐 아니라 메모리·상수 비용을 측정합니다. 데이터 변화율과 질의 종류가 구조 선택의 출발점입니다.