세그먼트 트리 구간 질의 계산기

어떤 구간이든 많아야 2·log₂n개 노드로 덮이기 때문입니다. 각 층에서 「구간에 완전히 들어가는 노드」로 쓰이는 것은 왼쪽 끝에 많아야 하나, 오른쪽 끝에 많아야 하나뿐입니다. 가운데는 부모가 통째로 삼키므로 더 내려갈 일이 없습니다. 층이 log₂n개이므로 합쳐서 2·log₂n개입니다.

결합법칙을 만족하는 연산이면 무엇이든 됩니다. 노드가 하는 일은 「왼쪽 답과 오른쪽 답을 합치는 것」뿐이라, 그 합치기만 결합법칙을 지키면 최솟값·최댓값·최대공약수·행렬 곱까지 같은 구조로 돌아갑니다. 교환법칙조차 필요 없고 왼쪽·오른쪽 순서만 지키면 됩니다.

세그먼트 트리는 역원이 필요 없다는 것이 가장 큰 차이입니다. 펜윅 트리는 구간 질의를 「r까지의 답 − (l−1)까지의 답」이라는 뺄셈으로 내므로 연산에 역원이 있어야 하고, 그래서 구간 최솟값에는 쓸 수 없습니다. 대신 펜윅은 코드가 훨씬 짧고 메모리를 덜 씁니다. 구간 합만 필요하면 펜윅, 최솟값·최댓값이 필요하면 세그먼트 트리입니다.

마지막 층이 비뚤어지는 n에서 가장 큰 노드 번호가 2n을 넘기 때문입니다. 뿌리를 1, 자식을 2i·2i+1로 매기면 n = 6, 10, 12, 18처럼 원소 수가 2의 거듭제곱이 아닐 때 잎이 한 층 더 내려가면서 번호가 커집니다. n이 2의 거듭제곱일 때는 딱 2n−1로 맞아떨어져서, 그런 값으로만 시험하면 놓치기 쉬운 사고입니다.

실제로 값이 들어 있는 노드는 2n−1개입니다. 잎이 n개이고 각 내부 노드가 자식을 정확히 둘 가지므로 내부 노드가 n−1개입니다. 다만 힙 색인으로 번호를 매기면 중간에 비는 번호가 생기므로 배열은 4n으로 잡습니다.

그 원소를 맡고 있는 노드가 잎에서 뿌리로 올라가는 한 줄뿐이기 때문입니다. 잎의 깊이가 ⌈log₂n⌉이므로 고칠 노드도 그만큼입니다. 최솟값·최댓값을 담고 있으면 값이 그대로인 노드도 나오는데, 다른 자식 쪽이 더 작거나 커서 답이 바뀌지 않은 경우입니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.