[BOJ 14438, Python] 数列とクエリ 17

問題リンク

[BOJ 14438](https://www.acmicpc.net/problem/14438

)

カテゴリ

セグメントツリー(segtree)、データ構造(data_structures)

説明

セグメントツリーを初めて学ぶ人が最もよく遭遇するセグメントツリー系の問題だと考えられる。

区間和、区間積、区間内の最大値など、様々な値について、線形リストを基準としたO(NlogN)の時間で構築でき、各区間に関する情報にO(logN)という高速な速度でアクセスできるという利点がある。

この問題は、大きく分けてセグメントツリーを構築する関数、区間情報を検索する関数、変更された値を反映する関数に分けることができる。

生成関数

まず、セグメントツリーを生成する関数

def make_segtree(target_list: list, result_list: list, start: int, end:int, now_node: int) -> int:
    '''
    최소 숫자 정보를 담는 세그먼트 트리를 생성하는 함수
    '''

    # 포인터가 한 곳으로 모인 경우
    if start == end:

        # 해당 노드는 포인터가 가리키는 인덱스의 값과 동일
        result_list[now_node] = target_list[start]

    # 포인터가 범위를 나타내는 경우
    else:

        # Devide and Conquer Algorithm

        # 중간 지점 선언
        mid = (start + end) // 2

        # 중간 지점을 기준으로 구간을 분할하여 최소값으로 갱신
        val_1 = make_segtree(target_list, result_list, start, mid, 2 * now_node)
        val_2 = make_segtree(target_list, result_list, mid + 1, end, 2 * now_node + 1)

        # 두 구간의 최소값을 비교하여 둘 중 최소값을 현재 노드에 기록
        result_list[now_node] = min(val_1, val_2)

    # 현재 노드의 값을 반환
    return result_list[now_node]

を見ると、基本的にはリスト全体を区間ごとに分割し、各区間に関する情報をセグメントツリーの各ノードに格納する過程を示している。

再帰方式を使用しているため、区間の長さが1になるまで再帰が進行するにつれて再帰スタックが積み上げられ、到達した場合はそのアドレスにリスト1つの値に関する情報を入力する。

その後、返された値を通じて、リーフノードではないノードは条件に合う値を選別しながら、最終的にルートに到達することになる。

したがって、ルートノードに含まれる値は、全区間において問題で要求された条件に最も適合する値となる。

探索関数

次に、区間内の最小値を探す関数について確認すると、

def find_min_number(target_tree: list, start: int, end: int, left: int, right: int, now_node: int) -> int:
    '''
    해당 구간의 최소값을 찾는 함수
    '''

    # 범위 내로 포인터가 좁혀진 경우
    if left <= start and right >= end:

        # 현재 노드값을 반환
        return target_tree[now_node]

    # 범위를 아예 벗어난 경우
    elif left > end or right < start:

        # None 값을 반환
        return None

    # 범위가 걸친 경우
    else:

        # Devide and Conquer Algorithm

        # 중간 지점 선언
        mid = (start + end) // 2

        # 중간 지점을 기준으로 구간을 분할하여 값을 확인
        val_1 = find_min_number(target_tree, start, mid, left, right, 2 * now_node)
        val_2 = find_min_number(target_tree, mid + 1, end, left, right, 2 * now_node + 1)

        # 반환된 값들 중 None이 존재하는 경우
        if val_1 is None and val_2 is None:
            return None

        elif val_1 is None:
            return val_2

        elif val_2 is None:
            return val_1

        # None이 없다면
        else:

            # 두 구간의 최소값 중에서 더 작은 값을 반환
            return min(val_1, val_2)

基本的に、探している区間が含まれている場所であれば詳細に処理を進め、完全に探している区間のみが含まれるようになるまで処理を行い、その値を返して親関数で確認できるようにコードを構成した。

もし範囲外の場合はNoneを返すようにし、条件を通じてPruningを行うだけで、完全に範囲内にある区間のみを選択して比較することができる。

修正関数

最後に、値の修正が行われた場合に反映する関数を見てみよう。

def change_segtree(target_tree: list, start: int, end: int, target_idx: int, target_val: int, now_node: int) -> None:
    '''
    리스트에 생긴 변경점을 트리에 반영하는 함수
    '''
    
    # 포인터가 한 곳으로 모인 경우
    if start == end:

        # 목표로 하는 인덱스랑 동일하다면 변경값을 반영
        if start == target_idx:
            target_tree[now_node] = target_val

    # 포인터가 범위로 주어진 경우
    else:

        # 목표 인덱스가 범위 내에 존재할 경우에만 갱신 가능성 존재
        if start <= target_idx <= end:

            # Devide and Conquer Algorithm

            # 중간 지점 선언
            mid = (start + end) // 2

            # 중간 지점을 기준으로 변경될 수 있는 인덱스를 재조사
            change_segtree(target_tree, start, mid, target_idx, target_val, 2 * now_node)
            change_segtree(target_tree, mid + 1, end, target_idx, target_val, 2 * now_node + 1)

        # 하위 노드들의 갱신이 진행된 이후 현재 노드의 갱신 진행
        target_tree[now_node] = min(target_tree[2 * now_node], target_tree[2 * now_node + 1])

現在変更された値のインデックスが含まれる区間であればすべて変更する必要があるため、そのインデックスを含む区間かどうかを基準に判別を行う。

生成関数と同様に、1つのインデックスに絞り込まれるまで再帰スタックを積み上げ、そのインデックス1つだけを含むノードの値の変更から返却を進めながら修正された値を反映し、最終的にルートノードまでチェックして完了することになる。

解答コード

上記の過程を通じて、問題で要求された動作をすべてモジュール化することができ、以下に全体コードを確認できる。

# 수열과 쿼리 17

import sys
from math import ceil, log2

input = sys.stdin.readline

def make_segtree(target_list: list, result_list: list, start: int, end:int, now_node: int) -> int:
    '''
    최소 숫자 정보를 담는 세그먼트 트리를 생성하는 함수
    '''

    # 포인터가 한 곳으로 모인 경우
    if start == end:

        # 해당 노드는 포인터가 가리키는 인덱스의 값과 동일
        result_list[now_node] = target_list[start]

    # 포인터가 범위를 나타내는 경우
    else:

        # Devide and Conquer Algorithm

        # 중간 지점 선언
        mid = (start + end) // 2

        # 중간 지점을 기준으로 구간을 분할하여 최소값으로 갱신
        val_1 = make_segtree(target_list, result_list, start, mid, 2 * now_node)
        val_2 = make_segtree(target_list, result_list, mid + 1, end, 2 * now_node + 1)

        # 두 구간의 최소값을 비교하여 둘 중 최소값을 현재 노드에 기록
        result_list[now_node] = min(val_1, val_2)

    # 현재 노드의 값을 반환
    return result_list[now_node]

def find_min_number(target_tree: list, start: int, end: int, left: int, right: int, now_node: int) -> int:
    '''
    해당 구간의 최소값을 찾는 함수
    '''

    # 범위 내로 포인터가 좁혀진 경우
    if left <= start and right >= end:

        # 현재 노드값을 반환
        return target_tree[now_node]

    # 범위를 아예 벗어난 경우
    elif left > end or right < start:

        # None 값을 반환
        return None

    # 범위가 걸친 경우
    else:

        # Devide and Conquer Algorithm

        # 중간 지점 선언
        mid = (start + end) // 2

        # 중간 지점을 기준으로 구간을 분할하여 값을 확인
        val_1 = find_min_number(target_tree, start, mid, left, right, 2 * now_node)
        val_2 = find_min_number(target_tree, mid + 1, end, left, right, 2 * now_node + 1)

        # 반환된 값들 중 None이 존재하는 경우
        if val_1 is None and val_2 is None:
            return None

        elif val_1 is None:
            return val_2

        elif val_2 is None:
            return val_1

        # None이 없다면
        else:

            # 두 구간의 최소값 중에서 더 작은 값을 반환
            return min(val_1, val_2)

def change_segtree(target_tree: list, start: int, end: int, target_idx: int, target_val: int, now_node: int) -> None:
    '''
    리스트에 생긴 변경점을 트리에 반영하는 함수
    '''
    
    # 포인터가 한 곳으로 모인 경우
    if start == end:

        # 목표로 하는 인덱스랑 동일하다면 변경값을 반영
        if start == target_idx:
            target_tree[now_node] = target_val

    # 포인터가 범위로 주어진 경우
    else:

        # 목표 인덱스가 범위 내에 존재할 경우에만 갱신 가능성 존재
        if start <= target_idx <= end:

            # Devide and Conquer Algorithm

            # 중간 지점 선언
            mid = (start + end) // 2

            # 중간 지점을 기준으로 변경될 수 있는 인덱스를 재조사
            change_segtree(target_tree, start, mid, target_idx, target_val, 2 * now_node)
            change_segtree(target_tree, mid + 1, end, target_idx, target_val, 2 * now_node + 1)

        # 하위 노드들의 갱신이 진행된 이후 현재 노드의 갱신 진행
        target_tree[now_node] = min(target_tree[2 * now_node], target_tree[2 * now_node + 1])

# 수열의 크기 및 수열 정보 입력
target_length = int(input())
target_arr = ['*'] + list(map(int, input().split()))

# 수열의 구간 최소 숫자를 담을 세그먼트 트리 리스트 선언
segtree_arr = [None for _ in range(pow(2, ceil(log2(target_length) + 1)))]

# 함수를 호출하여 트리 생성
make_segtree(target_arr, segtree_arr, 1, target_length, 1)

# 퀴리 갯수 입력 및 출력 리스트 선언
query_number = int(input())
output = []

# 쿼리 실행
for _ in range(query_number):

    # 각 쿼리의 정보
    order_type, num_1, num_2 = map(int, input().split())

    # 타입 1의 경우
    if order_type == 1:

        # 리스트 값을 변경 및 함수를 호출하여 트리에 반영
        target_arr[num_1] = num_2
        change_segtree(segtree_arr, 1, target_length, num_1, num_2, 1)

    # 타입 2의 경우
    elif order_type == 2:

        # 함수를 호출하여 해당 구간의 최소 숫자를 출력 리스트에 추가
        output.append(find_min_number(segtree_arr, 1, target_length, num_1, num_2, 1))

# 결과 출력
for result in output:
    print(result)