[ 알고리즘 ] 세그먼트 트리

📌 세그먼트 트리(Segment Tree)

여러 개의 데이터가 존재할 때 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조.

트리 종류 중에 하나로 이진 트리의 형태이며, 특정 구간의 합을 가장 빠르게 구할 수 있다는 장점이 있다. (O(logN))

🐛 선형 구조로 구할 때 O(N)

  array = [1,2,3,4,5,6,7,8,9,10]
  for i in range(1,len(array)):
  	array[i] += array[i-1]

좌측의 데이터에 현재의 데이터를 더해가면서 구간 합 배열을 생성한다.

출력 과정 O(1)

🚀 세그먼트 트리로 구할 때 O(logN)

start와 end가 같아지는 순간에 ARRAY에 있는 값을 tree에 넣어 준다는 것을 눈여겨 봐야한다.

또한 재귀적으로 현재 인덱스에 좌측과 우측 자식노드의 값을 더해주게 된다.

    N = 10
    Array = [1,2,3,4,5,6,7,8,10]
    tree = [0]*(N*4)
    
    def init(start, end, index):
    	# 가장 끝에 도달 했으면 Array를 삽입
    	if start == end: 
            tree[index] = Array[start]
            return tree[index]
        mid = (start + end) // 2
        # 좌측 노드와 우측 노드를 합친다.
        tree[index] = init(start,mid,index*2) + init(mid+1,end,index*2+1)
        
    def query(start, end, index, qLeft, qRight):
    	# 범위를 벗어나는 경우
        if qLeft > end or qRight < start:
        	return 0
        # 범위 내에 있는 경우
        if qLeft <= start and end <= qRight:
        	return tree[index]
        mid = (start + end) // 2
        return query(start,mid,index*2,qLeft,qRight) + query(mid+1, end, index*2+1, qLeft, qRight)
    
    # 부모 노드 인덱스 1부터 시작
    init(1,N,1)
    s ,e = map(int,input().split())
    print(query(1,N,1,s,e))