1. 언제 쓰이는가

구간합을 빠르게 구하고 해당 구간에 갱신을 가장 빠르게 처리 하기 위함

세그먼트 트리로 구간 합을 구하거나 수정을 하면 O(logn)의 시간복잡도로 구간의 합을 구하는게 가능해진다.

2. 아라보자

예시 ) 크기가 11인 배열의 합을 다음과 같이 구간의 합을 트리형태로 저장한다

complete tree이기 때문에

*왼쪽 자식 = node 2

오른 쪽 자식 = node 2+1

2~8까지 구간의 합을 구하기 위해 탐색하는 노드를 표시햅

모든 노드를 탐색하지 않고 빠르게 구간합을 구할 수 있다.

3. Sample code (swift)

import Foundation
struct SegmentTree{
    var n:Int //구하고자 할 배열의 크기
    var tree:[Int] // 합을 저장하기 위한 배열 컴프리트 트리의 성질로 인해 배열로 가능함
    
    func merge(_ left:Int, _ right:Int)->Int{
        return left+right
    }
    mutating func buildRec(_ arr:[Int], _ node:Int, _ left:Int, _ right:Int)->Int{
        if left==right{
            tree[node] = arr[left]
            return tree[node]
        }
        let mid = left + (right-left)/2
        let leftValue = buildRec(arr, node*2, left, mid)
        let rightValue = buildRec(arr, node*2+1, mid+1, right)
        tree[node] = merge(leftValue, rightValue)
        return tree[node]
    }
    mutating func build(arr:[Int], size:Int){
        n=size
        tree = Array.init(repeating: 0, count: n*4)// 보통원래배열보다 4배크면 구현가능하다함
        buildRec(arr, 1, 0, n-1)//1번 노드부터 시작
    }
    func query_rec(_ node:Int, _ nodeLeft:Int, _ nodeRight:Int, _ left:Int, _ right:Int )->Int{
        //방문이 필요없는 구간이면 리턴
				if right<nodeLeft || nodeRight<left{
            return 0;
        }
				// 구하고자 하는 구간에 속하면 더 방문하지 않고 리턴
        if left<=nodeLeft && nodeRight<=right{
            return tree[node]
        }
				//전체 구간에서 반반씩 나눠가면서 다시 제귀적으로 호출
        let mid = nodeLeft + (nodeRight-nodeLeft)/2
        return merge(query_rec(node*2, nodeLeft, mid, left, right),query_rec(node*2+1, mid+1, nodeRight, left, right))
    }
    func query(_ left:Int, _ right:Int )->Int{
        return query_rec(1, 0, n, left, right)
    }

}

let arr = [1,3,11,6,7,19,14,9,18,16,5,4,2,8,19]
var sgTree = SegmentTree(n: arr.count, tree: [])
sgTree.build(arr: arr, size: arr.count)
print(sgTree.query(1, 10))
print((1...10).reduce(0){$0+arr[$1]})

4. 사람들이 똑똑하다