누적 합을 위한 펜윅 트리
log n에 점 갱신과 누적 질의를 수행합니다
누적 합을 위한 펜윅 트리은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
접두사 배열이 무너지는 이유
일반적인 접두사 합 배열은 구간에 즉시 답할 수 있지만, 한 번만 갱신해도 배열을 다시 만들어야 합니다. 갱신이 많으면 매우 느려집니다. ⏱️
펜윅 트리의 등장
펜윅 트리, 즉 BIT는 점 갱신과 접두사 질의를 모두 O(log n)에 처리합니다. 동적으로 누적 합을 계산할 때 가장 먼저 고려할 자료 구조입니다.
처음부터 1로 인덱싱하기
펜윅 트리는 인덱스가 1부터 시작하는 배열에 저장됩니다. 인덱스 0은 사용하지 않는 감시 값으로 두므로 실제 데이터는 모두 위치 1부터 시작합니다.
tree = [0] * (n + 1)최하위 설정 비트의 마법
각 인덱스는 값의 한 블록을 담당합니다. 블록 크기는 i의 최하위 설정 비트인 i & -i와 같습니다. 이 한 가지 요령이 트리 전체를 작동하게 합니다.
lowbit = i & -i하나의 위치 갱신하기
위치 i에 값을 더하려면 매 단계마다 최하위 설정 비트만큼 앞으로 이동하면서 i를 포함하는 모든 블록을 갱신합니다.
while i <= n:
tree[i] += delta
i += i & -i접두사 합 질의하기
처음 i개의 값을 더하려면 매 단계마다 최하위 설정 비트만큼 뒤로 이동하여 0에 도달할 때까지 진행합니다.
s = 0
while i > 0:
s += tree[i]
i -= i & -i두 반복문 모두 로그 시간
각 반복에서 비트 하나를 끄므로 최대 log n번만 실행됩니다. 이것이 갱신과 질의가 모두 빠르게 유지되는 이유입니다.
두 접두사로 구간 합 구하기
l부터 r까지의 합이 필요하신가요? 정적 접두사 배열과 마찬가지로 r까지의 접두사 합 - (l-1)까지의 접두사 합을 계산하면 됩니다. 이제 갱신도 저렴합니다.
range_sum = query(r) - query(l - 1)트리 만들기
가장 단순한 방법은 각 초기값에 대해 갱신을 호출하는 것입니다. 이는 O(n log n)이며 대부분의 대회에서 충분히 빠릅니다.
for i, v in enumerate(a, 1):
update(i, v)아주 작은 메모리 사용량
펜윅 트리에는 크기 n+1인 배열 하나만 필요합니다. 이러한 간결한 메모리 사용량 덕분에 대회에서 많은 사랑을 받습니다. 💾
BIT를 선택할 때
점 갱신과 접두사 합 또는 구간 합 질의를 번갈아 처리해야 한다면 펜윅 트리를 선택하십시오. 작성할 코드가 짧고 성능 면에서도 따라올 방법이 드뭅니다.
빠른 확인
반복문이 어떻게 이동하는지 확실히 익혀 봅시다.
복습: BIT 기초
펜윅 트리를 배웠습니다. 인덱스는 1부터 시작하고 i & -i를 기반으로 하며, 점 갱신과 접두사 질의가 모두 O(log n)에 이루어집니다. 다음에는 이를 사용해 역순쌍을 세어 보겠습니다. 🎯
자주 묻는 질문
“누적 합을 위한 펜윅 트리” 강의는 무료인가요?
네 — “누적 합을 위한 펜윅 트리” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“누적 합을 위한 펜윅 트리”에서 뭘 배우나요?
log n에 점 갱신과 누적 질의를 수행합니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“누적 합을 위한 펜윅 트리” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 누적 합을 위한 펜윅 트리
- BIT를 이용한 역전쌍
- 세그먼트 트리: 구축과 질의
- 구간 갱신을 위한 지연 전파