Iterative Segment Tree (Range Minimum Query)

---

1. 개요 및 특징

• 목적: 배열의 특정 구간 최소값(RMQ)을 $O(\log N)$에 구하고, 점 업데이트(Point Update)를 $O(\log N)$에 수행
• 반복문(Iterative) 방식의 장점:
  • 재귀 호출 오버헤드가 없어 실행 속도가 빠르고 메모리 사용량이 적음
  • 구현이 매우 간결함 (1-indexed 기반 배열)
• 공간 복잡도: $O(N)$ (크기 $2N$의 배열 사용)
• 시간 복잡도:
  • 트리 생성: $O(N)$
  • 점 업데이트 (Point Update): $O(\log N)$
  • 구간 쿼리 (Range Query): $O(\log N)$

---

2. 배열 인덱싱 및 트리 구조

크기 $N$인 원본 배열에 대해 크기 $2N$의 segtree 배열을 할당.

• 리프 노드 (Leaf Nodes): segtree[N] ~ segtree[2N - 1]
  • 원본 배열 a[i]는 segtree[N + i]에 위치

• 내부 노드 (Internal Nodes): segtree[1] ~ segtree[N - 1]
  • 부모 노드: i / 2 (i >> 1)
  • 왼쪽 자식: 2 * i (i << 1)
  • 오른쪽 자식: 2 * i + 1 ((i << 1) | 1)

---

3. 핵심 알고리즘 구현 (C++)

(1) 트리 생성 (Construction)

리프 노드에 값을 채운 뒤, $N-1$부터 $1$까지 역순으로 올라가며 부모 노드 채움.

void construct_segment_tree(vector<int>& segtree, const vector<int>& a, int n) {
    // 1. 리프 노드 채우기
    for (int i = 0; i < n; i++) {
        segtree[n + i] = a[i];
    }
    // 2. 내부 노드 채우기 (Bottom-up)
    for (int i = n - 1; i >= 1; i--) {
        segtree[i] = min(segtree[2 * i], segtree[2 * i + 1]);
    }
}

---

(2) 점 업데이트 (Point Update)

특정 인덱스 pos의 값을 value로 변경 후 부모 노드들을 갱신.

void update(vector<int>& segtree, int pos, int value, int n) {
    pos += n; // 리프 노드 위치로 이동
    segtree[pos] = value;

    // 부모 노드들을 따라 올라가며 갱신
    while (pos > 1) {
        pos >>= 1; // 부모 이동 (pos / 2)
        segtree[pos] = min(segtree[2 * pos], segtree[2 * pos + 1]);
    }
}

---

(3) 구간 최솟값 쿼리 (Range Minimum Query)

반개폐 구간 [left, right) 기준으로 처리. (left부터 right - 1까지의 최솟값)

• left가 홀수(오른쪽 자식)면 해당 노드 값을 결과에 포함하고 left++ 한 뒤 위 단계로 이동
• right가 홀수(오른쪽 자식)면 right-- 후 해당 노드 값을 결과에 포함하고 위 단계로 이동

// 그려보면 쉽게 이해 된다.
int range_query(vector<int>& segtree, int left, int right, int n) {
    left += n;
    right += n;
    int min_val = 1e9; // 충분히 큰 값으로 초기화

    while (left < right) {
        if (left & 1) { // left가 홀수인 경우 (오른쪽 자식 노드)
            min_val = min(min_val, segtree[left]);
            left++;
        }
        if (right & 1) { // right가 홀수인 경우
            right--;
            min_val = min(min_val, segtree[right]);
        }
        left >>= 1;  // 다음 레이어로 이동 (left / 2)
        right >>= 1; // 다음 레이어로 이동 (right / 2)
    }
    return min_val;
}

주의: 닫힌 구간 [l, r]의 최솟값을 구할 때는 range_query(segtree, l, r + 1, n)으로 인자 전달.

---