Algorithm - 세그먼트 트리 Segment Tree(파이썬/Python)

Algorithm - 세그먼트 트리 Segment Tree(파이썬/Python)

import math

nums = [ 1 , 2 , 3 , 4 , 5 ]

n = len (nums) # leaf node의 개수

h = math.ceil(math.log(n, 2 )) # 밑이 2인 logN

segmentSize = 2 * * (h + 1 ) - 1 # 높이가 h일때 노드의 최대 개수

segmentSize + = 1 # 시작 index를 1로 할 것이므로 +1

def init(nums, tree, node, start, end): # nums 배열, tree 배열, tree의 index, 시작 index, 끝 index

if start = = end:

tree[node] = nums[start]

else :

mid = (start + end) / / 2

tree[node] = init(nums, tree, node * 2 , start, mid) + init(nums, tree, node * 2 + 1 , mid + 1 , end)

return tree[node]

# 특정 index의 값을 변경

def update(tree, node, diff, index, start, end): # 배열의 누적합을 저장하므로 diff를 이용해서 누적합을 구해야함

if index < start or index > end: # index가 start와 end 사이에 있지 않다면 계산할 필요 x

return

tree[node] + = diff

if start ! = end:

mid = (start + end) / / 2

update(tree, node * 2 , diff, index, start, mid)

update(tree, node * 2 + 1 , diff, index, mid + 1 , end)

# 특정 구간의 합을 출력

def sum(tree, node, left, right, start, end): # left부터 right까지의 합을 출력

# 1. left, right가 범위 start, end를 벗어나는 경우

if left > end or right < start:

return 0

# 2. left, right에 범위 start, end가 완전히 포함되는경우

if left < = start and end < = right:

return tree[node]

# 3. left, right가 범위 start, end에 일부만 포함되는 경우

mid = (start + end) / / 2

from http://nooblette.tistory.com/263 by ccl(A) rewrite - 2021-10-14 19:00:38