세그먼트 트리: 구축과 질의
log n에 구간 최솟값, 최댓값 또는 합을 구합니다
세그먼트 트리: 구축과 질의은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
펜윅 트리 너머
펜윅 트리는 합 계산에 뛰어나지만, 세그먼트 트리는 최솟값, 최댓값, 최대공약수 등을 처리합니다. 구간 질의를 위한 유연한 만능 도구입니다.
구간 위에 놓인 트리
각 노드는 배열의 구간 하나를 담당합니다. 루트는 전체를 포함하고, 자식 노드는 리프가 하나의 원소를 담을 때까지 구간을 절반씩 나눕니다.
배열 기반 저장
트리를 크기 2n 또는 4n인 평평한 배열에 저장합니다. 노드 1이 루트이고, 노드 i의 자식은 2i와 2i+1에 놓입니다.
seg = [0] * (2 * n)리프에 데이터 저장하기
반복형 구조에서는 원래 값이 배열의 뒤쪽 절반, 즉 n부터 2n-1까지의 인덱스에 저장됩니다.
for i in range(n):
seg[n + i] = a[i]아래에서 위로 만들기
각 내부 노드는 두 자식의 combine 결과입니다. n-1부터 1까지 채우면 전체 트리가 완성됩니다.
for i in range(n - 1, 0, -1):
seg[i] = seg[2*i] + seg[2*i+1]Combine 연산
combine 함수가 트리의 동작을 정의합니다. 합에는 덧셈을, 최솟값에는 최솟값 연산을, 최댓값에는 최댓값 연산을 사용하십시오. 이 연산을 바꾸면 질의도 바뀝니다.
def combine(x, y):
return min(x, y)점 갱신 후 위로 올라가기
하나의 값을 바꾸려면 리프를 설정한 뒤 루트까지 올라가면서 두 자식으로부터 각 부모를 다시 계산합니다.
i += n
seg[i] = value
while i > 1:
i //= 2
seg[i] = combine(seg[2*i], seg[2*i+1])반열린 구간 질의하기
구간 질의는 양쪽 끝에서 훑으며 경계 노드를 결과에 누적합니다. 구간은 반열린 구간으로, l부터 r 바로 전까지를 포함합니다.
반복형 질의 반복문
l과 r을 서로를 향해 이동시킵니다. 인덱스가 홀수 경계를 나타내면 포인터를 이동하기 전에 해당 노드를 결과에 포함합니다.
while l < r:
if l & 1: res = combine(res, seg[l]); l += 1
if r & 1: r -= 1; res = combine(res, seg[r])
l //= 2; r //= 2양쪽 모두 로그 시간
만들기는 O(n)이고, 각 갱신과 질의는 O(log n)입니다. 이러한 균형 덕분에 세그먼트 트리가 매우 다재다능합니다.
항등원에 유의하기
결과를 연산의 항등원에서 시작하십시오. 합은 0, 최솟값은 양의 무한대, 최댓값은 음의 무한대입니다. 시작값이 잘못되면 답도 잘못됩니다.
res = float('inf')빠른 확인
반복형 트리에서 원래 데이터는 어디에 저장됩니까?
복습: 유연한 구간
세그먼트 트리를 만들었습니다. 리프는 뒤쪽 절반에 있고, 부모는 combine 결과이며, 합·최솟값·최댓값에 대한 갱신과 질의를 O(log n)에 처리합니다. 🌳
자주 묻는 질문
“세그먼트 트리: 구축과 질의” 강의는 무료인가요?
네 — “세그먼트 트리: 구축과 질의” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“세그먼트 트리: 구축과 질의”에서 뭘 배우나요?
log n에 구간 최솟값, 최댓값 또는 합을 구합니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“세그먼트 트리: 구축과 질의” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 누적 합을 위한 펜윅 트리
- BIT를 이용한 역전쌍
- 세그먼트 트리: 구축과 질의
- 구간 갱신을 위한 지연 전파