세그먼트 트리

세그먼트 트리(Segment Tree)는 구간에 대한 쿼리(예: 합, 최소값, 최대값 등)를 효율적으로 처리하기 위해 사용되는 자료구조입니다. 이 자료구조는 부분합 쿼리와 같은 문제에서 유용하며, 특히 값의 업데이트와 쿼리를 모두 효율적으로 처리해야 하는 상황에 적합합니다.

1. 세그먼트 트리의 특징

• 시간 복잡도
• 쿼리 처리 및 업데이트: 
• 초기 트리 빌드: 
• 사용 조건
• 주어진 배열이 변동될 수 있을 때(업데이트가 자주 발생할 때)
• 배열의 특정 구간에 대한 질의(쿼리)를 자주 수행할 때
• 트리의 크기
• 배열의 크기를 이라고 할 때, 세그먼트 트리의 크기는  정도로 메모리를 할당하는 것이 일반적입니다.

2. 세그먼트 트리의 구성

• 세그먼트 트리는 이진 트리 구조를 기반으로 하며, 리프 노드는 배열의 각 원소에 대응됩니다.
• 각 내부 노드는 자신의 두 자식 노드에 기반하여 구간 정보를 저장합니다.
• 예: 구간의 합을 저장하려면 부모 노드 = 

트리의 인덱스 구조

• 루트 노드의 인덱스: 1 (0-based로 구현하는 경우도 있음)
• 번째 노드의:
• 왼쪽 자식: 
• 오른쪽 자식: 
• 부모 노드: 

3. 세그먼트 트리의 주요 연산

(1) 빌드(Build)

배열을 기반으로 세그먼트 트리를 초기화합니다.

def build_tree(arr, tree, node, start, end):
    if start == end:  # 리프 노드
        tree[node] = arr[start]
    else:
        mid = (start + end) // 2
        build_tree(arr, tree, 2 * node, start, mid)  # 왼쪽 자식
        build_tree(arr, tree, 2 * node + 1, mid + 1, end)  # 오른쪽 자식
        tree[node] = tree[2 * node] + tree[2 * node + 1]  # 부모 노드 값

(2) 구간 쿼리(Query)

배열의 특정 구간에 대한 질의를 수행합니다.

def query(tree, node, start, end, l, r):
    if r < start or end < l:  # 완전히 겹치지 않는 경우
        return 0  # 합을 구할 경우, 무효값 반환
    if l <= start and end <= r:  # 완전히 포함되는 경우
        return tree[node]
    mid = (start + end) // 2
    left_sum = query(tree, 2 * node, start, mid, l, r)
    right_sum = query(tree, 2 * node + 1, mid + 1, end, l, r)
    return left_sum + right_sum

(3) 업데이트(Update)

배열의 특정 값을 변경하고 트리를 갱신합니다.

def update(tree, node, start, end, idx, val):
    if start == end:  # 리프 노드 도달
        tree[node] = val
    else:
        mid = (start + end) // 2
        if start <= idx <= mid:  # 왼쪽 자식 갱신
            update(tree, 2 * node, start, mid, idx, val)
        else:  # 오른쪽 자식 갱신
            update(tree, 2 * node + 1, mid + 1, end, idx, val)
        tree[node] = tree[2 * node] + tree[2 * node + 1]  # 부모 노드 갱신

4. 응용

세그먼트 트리는 다양한 문제를 해결할 수 있습니다. 다음은 세그먼트 트리로 해결할 수 있는 몇 가지 문제입니다:
1. 구간 합 구하기
2. 구간 최대/최소값 찾기
3. 구간 XOR/AND/OR 계산
4. 구간 곱 계산 (모듈러 연산 포함)
5. 구간 업데이트 및 쿼리 (Lazy Propagation 적용)

5. 세그먼트 트리의 변형

• Lazy Propagation
구간 업데이트를 효율적으로 처리하기 위한 기법입니다. 업데이트를 즉시 적용하지 않고 필요할 때 적용합니다.
• 2D 세그먼트 트리
2차원 배열에 대한 구간 질의를 처리합니다.  시간 복잡도를 가집니다.

예제

배열 에 대해 세그먼트 트리를 구성하고, 구간 합 및 값을 업데이트하는 코드

# 입력 배열
arr = [1, 3, 5, 7, 9, 11]
n = len(arr)

# 세그먼트 트리 초기화
tree = [0] * (4 * n)

# 빌드
build_tree(arr, tree, 1, 0, n - 1)

# 구간 합 쿼리: 구간 [1, 3]
print(query(tree, 1, 0, n - 1, 1, 3))  # 출력: 15 (3+5+7)

# 값 업데이트: arr[1] = 10
update(tree, 1, 0, n - 1, 1, 10)

# 업데이트 후 구간 합 쿼리: 구간 [1, 3]
print(query(tree, 1, 0, n - 1, 1, 3))  # 출력: 22 (10+5+7)

세그먼트 트리는 효율성과 유연성 때문에 알고리즘 대회와 실무에서 중요한 자료구조로 사용됩니다.