import math
# 이해법
# 첫번쨰 build로 계속 타고 들어가서 끝에 도달
# 이분법으로 범위를 쪼게서 들어왔음을 고려
# 마지막에선 좌 우 하나씩만 범위를 가져올거기 때문에
# 두번째 build로 들어가서 두번째 값을 넣어주곤 나옴
# 두 build의 연산이 끝났기 때문에 부모 node에 합을 넣어줌
# 예를들어 0~20 범위일때
# 0~20 -> 0~10, 11~20
# 0~10 -> 0~5, 6~10
# 0~5 -> 0~2, 2~5
# 0~2 -> 0~1, 2
# 0~1 -> 0, 1
# 0, 1 찍고 합처리
# 2찍고 합처리
# 2~5 시작
# 2~5 -> 2~3, 3~4
# 2~3 -> 2, 3
# 2, 3 찍고 합처리
# 3~4 -> 3, 4
# 3, 4 찍고 합처리
# 두 합을 더해줌
# 위의 0~2, 2~5 마지막에 나온 수 합처리
# 6~10 시작
# ....
def build(arr, tree, node, start, end):
if start == end:
tree[node] = arr[start]
else:
mid = (start + end) // 2
build(arr, tree, node * 2, start, mid)
build(arr, tree, node * 2 + 1, mid + 1, end)
tree[node] = tree[node * 2] + tree[node * 2 + 1]
# idx까지 타고 들어가는 경로까지만 diff만큼 더해줌
def update(tree, node, start, end, idx, diff):
if idx < start or idx > end:
return
tree[node] += diff
if start != end:
mid = (start + end) // 2
update(tree, node * 2, start, mid, idx, diff)
update(tree, node * 2 + 1, mid + 1, end, idx, diff)
# 이분하면서 우측 범위가 해당 범위에 전부 포함되면 그대로 반환
# 5~20이면 11~20은 바로 합 반환 5~10은 새로 구하는데
# 0~10 -> 0~5 6~10 -> 6~10은 바로 반환
# 5만 찾아서 더해줌
def query(tree, node, start, end, left, right):
if right < start or end < left:
return 0
if left <= start and end <= right:
return tree[node]
mid = (start + end) // 2
return query(tree, node * 2, start, mid, left, right) + query(tree, node * 2 + 1, mid + 1, end, left, right)
# 예제 데이터
arr = [1, 3, 5, 7, 9, 11]
n = len(arr)
# 트리 크기 공식 적용
h = math.ceil(math.log2(n)) # 트리 높이
tree_size = 2 ** (h + 1) # 최대 노드 개수 (2^(h+1) - 1)
tree = [0] * tree_size # 세그먼트 트리 배열
# 트리 초기화
build(arr, tree, 1, 0, n - 1)
# 1. 구간 합 (3번째 ~ 5번째 값의 합) = 5 + 7 + 9 = 21
print("구간 합(3~5):", query(tree, 1, 0, n - 1, 2, 4)) # 출력: 21
# 2. 3번째 값(5)을 6으로 변경
idx = 2 # 0-based index
new_value = 6
diff = new_value - arr[idx]
arr[idx] = new_value
update(tree, 1, 0, n - 1, idx, diff)
# 3. 변경 후 다시 구간 합 (3번째 ~ 5번째 값의 합) = 6 + 7 + 9 = 22
print("구간 합(3~5, 변경 후):", query(tree, 1, 0, n - 1, 2, 4)) # 출력: 22
