이론: 세그먼트 트리

[fineman999]

구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태

[fineman999]

세그먼트 트리의 핵심 이론

• 세그먼트 트리의 종류는 구간 합, 최대 최소 구하기로 나눌 수 있고, 구현 단계는 트리 초기화하기, 질의 값 구하기(구간 합 또는 최대 최소), 데이터 업데이트하기로 나눌 수 있음

[fineman999]

1. 트리 초기화 하기

• 리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 구함 -> 이때 리프 노드가 기존의 데이터들이고, 나머지 노드들은 조건을 위해서 있음
• 트리의 높이를 구해야됨 -> 왜냐? -> 우리는 트리를 일차원 배열로 나타내기 때문에 -> 그래서 끝에서부터 채울거임

[fineman999]

트리 높이 구하는 방법

2의 k승 >= N을 만족하는 k의 최솟값을 구한 후 (2의 k승) 2를 트리 배열의 크기로 정하면 됨 예로 N이 8이면 k는 3이 되고 배열의 크기는 (2의 3승) 2 = 16이 된다.

• 이진트리를 나타내기 때문

  height = int(math.pow(2, math.ceil(math.log2(n))) * 2)

[fineman999]

리프 노드에 샘플 데이터 넣기

samples = [5, 8, 4, 3, 7, 2, 1, 6]

은 어디에 넣을까 처음에 구한 값 2의 k승이 start index값이다. ex 2의 3 = 8 8부터 시작

    start_index = int(math.pow(2, k))
    cnt = 0
    while cnt < len(samples):
        graph[start_index + cnt] = samples[cnt]
        cnt += 1

[fineman999]

나머지 노드 데이터 넣기

• 채워야하는 인덱스가 N이라고 가정하면 자신의 자식 노드를 이용해 해당 값을 채울 수 있음. 자식 노드의 인덱스는 이진 트리 형식이기 때문에 2N, 2N + 1이 됨.
• 이 방식으로 뒤에서부터 2개씩 묶어서 나누기 2한 정수 값에 기존 값을 2까지 진행한다.

[fineman999]

2. 질의값 구하기

• 주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경합니다. 기존 샘플을 기준으로 한 인덱스값과 세그먼트 트리 배열에서의 인덱스값이 다르기 때문에 인덱스를 변경해야함
• 예를 들어 1 ~ 4이면 리프노드로 8 ~ 11로 변경해야됨

  질의 인덱스를 세그먼트 트리 인덱스로 변경하는 방법

• 세그먼트 트리 index = 주어진 질의 index + 2의 k승 - 1

[fineman999]

질의값 구하는 과정

1. start_index % 2 == 1일 때 해당 노드를 선택한다.
2. end_index % 2 == 0 일 때 해당 노드를 선택한다.
3. start_index depth 변경: start_index = (start_index + 1) / 2 연산을 실행한다.
4. end_index depth 변경: end_index = (end_index -1) / 2 연산을 실행한다.
5. 1 ~ 4를 반복하다가 end_index < start_index가 되면 종료한다.

[fineman999]

설명

• 1번 문항에서 1일 때 선택한다는 의미는 1일 경우 2개의 노드 중 오른쪽에 있는 노드이므로 왼쪽 노드는 필요 없으므로 독립적으로 선택한다는 의미이다.
• 3번은 왼쪽과 오른쪽 노드 상관없이 +1을 하면 원하는 부모 노드로 가리키게 된다.
• 1번과 2번에 해당되는 값이 없으면 부모 노드에서 해당 값을 계산하므로 넘어가게 된다.