C++ 세그먼트 트리로 배열 최소·최대 범위 쿼리 구현하기

문제 개요

N개의 원소로 이루어진 배열 Arr[]가 주어졌을 때, 쿼리로 지정된 인덱스 범위 안에서 최솟값과 최댓값을 찾아내는 것이 목표입니다.

각 쿼리에는 탐색을 시작할 인덱스(QStart)와 끝낼 인덱스(QEnd)가 함께 전달됩니다.

예시

입력 — Arr[] = { 1, 2, 3, 4, 5 }, QStart = 1, QEnd = 4

출력

최솟값 : 2
최댓값 : 5

설명 — 위 쿼리의 시작 인덱스는 1, 끝 인덱스는 4입니다. 이 두 인덱스 사이 구간에서 Arr의 최솟값은 2, 최댓값은 5입니다.

입력 — Arr[] = { 10, 12, 3, 2, 5, 18 }, QStart = 2, QEnd = 5

출력

최솟값 : 2
최댓값 : 18

설명 — 위 쿼리의 시작 인덱스는 2, 끝 인덱스는 5입니다. 이 구간에서 Arr의 최솟값은 2, 최댓값은 18입니다.

프로그램에 적용된 접근 방식

이 접근 방식에서는 세그먼트 트리(Segment Tree)를 활용해 주어진 쿼리 범위 내의 최솟값과 최댓값을 효율적으로 찾습니다. 단순히 구간을 일일이 순회하는 방식(O(N))과 달리, 세그먼트 트리를 사용하면 쿼리 하나를 O(log N) 시간에 처리할 수 있어 같은 배열에 여러 번의 범위 쿼리가 들어오는 상황에서 특히 유용합니다.

입력 배열 Arr[]와 쿼리 인덱스 QStart, QEnd를 받습니다.
결과는 value 타입으로 저장합니다.
구조체 value는 쿼리 범위에서 찾은 최솟값(minVal)과 최댓값(maxVal)을 담는 역할을 합니다.
함수 minMax(struct value *root1, int num, int qStart1, int qEnd1)는 쿼리 인덱스를 받아 qStart1부터 qEnd1 사이의 최솟값과 최댓값을 구합니다.
(qStart1 < 0 또는 qEnd1 > num-1 또는 qStart1 > qEnd1) 조건을 검사해 참이면 쿼리 범위가 유효하지 않다고 알립니다.
범위가 유효하면 minmaxFind(root1, 0, num-1, qStart1, qEnd1, 0)을 호출합니다.
함수 minmaxFind(struct value *root, int startT, int endT, int qStart, int qEnd, int pos)는 재귀 함수로, 세그먼트 트리의 루트 포인터와 현재 노드가 담당하는 구간의 시작(startT)·끝(endT) 인덱스를 인자로 받습니다.
쿼리 범위의 시작·끝 인덱스도 함께 전달되며, 현재 노드의 위치는 pos입니다.
(qStart <= startT)이고 (qEnd >= endT)라면 현재 노드의 구간이 쿼리 범위에 완전히 포함되므로, 해당 구간의 최솟값과 최댓값을 그대로 반환합니다.
현재 구간이 쿼리 범위 밖이라면 minVal과 maxVal을 무효 값으로 초기화해 반환합니다.
현재 구간이 쿼리 범위와 일부만 겹친다면 다음 과정을 수행합니다.
middl = startT + (endT - startT)/2 로 중간 지점을 계산합니다.
p1 = 2*pos+1, p2 = 2*pos+2 로 왼쪽·오른쪽 자식 노드의 위치를 정합니다.
lpos = minmaxFind(root, startT, middl, qStart, qEnd, p1), rpos = minmaxFind(root, middl+1, endT, qStart, qEnd, p2)로 양쪽 자식을 재귀 호출합니다.
temp.minVal은 lpos.minVal과 rpos.minVal 중 더 작은 값으로 설정합니다.
temp.maxVal은 lpos.maxVal과 rpos.maxVal 중 더 큰 값으로 설정합니다.
temp를 반환합니다.
함수 segmentTree(int arr2[], int startT2, int endT2, struct value *root2, int pos2)는 배열 arr2[]에 대해 [startT2, endT2] 구간을 담당하는 세그먼트 트리를 재귀적으로 구축합니다.
함수 *createTree(int arr0[], int num0)는 주어진 배열 arr0로 세그먼트 트리를 생성합니다. 필요한 메모리를 할당한 뒤 segmentTree()를 호출해 트리를 채웁니다.

세그먼트 트리 구축에는 O(N)의 시간이 걸리고, 이후 각 범위 쿼리는 O(log N)에 처리됩니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
struct value{
    int minVal;
    int maxVal;
};
struct value minmaxFind(struct value *root, int startT, int endT, int qStart,
    int qEnd, int pos){
    struct value temp, lpos ,rpos;
    if (qStart <= startT) {
        if( qEnd >= endT)
            { return root[pos]; }
    }
    if (endT < qStart || startT > qEnd) {
        temp.minVal = 9999;
        temp.maxVal = -9999;
        return temp;
    }
    int middl = startT + ( endT - startT )/2;
    int p1=2*pos+1;
    int p2=2*pos+2;
    lpos = minmaxFind(root, startT, middl, qStart, qEnd, p1);
    rpos = minmaxFind(root, middl+1, endT, qStart, qEnd, p2);
    temp.minVal = (lpos.minVal<rpos.minVal) ? lpos.minVal : rpos.minVal ;
    temp.maxVal = (lpos.maxVal>rpos.maxVal) ? lpos.maxVal : rpos.maxVal ;
    return temp;
}
struct value minMax(struct value *root1, int num, int qStart1, int qEnd1){
    struct value temp1;
    if (qStart1 < 0 || qEnd1 > num-1 || qStart1 > qEnd1){
        cout<<"Please enter Valid input!!";
        temp1.minVal = 9999;
        temp1.maxVal = -9999;
        return temp1;
    }
    return minmaxFind(root1, 0, num-1, qStart1, qEnd1, 0);
}
void segmentTree(int arr2[], int startT2, int endT2, struct value *root2, int pos2){ 
    if (startT2 == endT2) { 
        root2[pos2].minVal = arr2[startT2];
        root2[pos2].maxVal = arr2[startT2];
        return ;
    }
    int p1=pos2*2+1;  
    int p2=pos2*2+2;
    int middl2 = startT2+(endT2-startT2)/2;
    segmentTree(arr2, startT2, middl2, root2, p1);
    segmentTree(arr2, middl2+1, endT2, root2, p2);
    root2[pos2].minVal = root2[p1].minVal<root2[p2].minVal ? root2[p1].minVal : root2[p2].minVal;
    root2[pos2].maxVal = root2[p1].maxVal>root2[p2].maxVal ? root2[p1].maxVal : root2[p2].maxVal;
}
struct value *createTree(int arr0[], int num0) { 
    int height = (int)(ceil(log2(num0)));
    int maxS = 2*(int)pow(2, height) - 1;
    struct value *root0 = new struct value[maxS];
    segmentTree(arr0, 0, num0-1, root0, 0);
    return root0;
}
int main() { 
   int Arr[] = { 1, 2, 3, 4, 5 };
   int length = sizeof(Arr)/sizeof(Arr[0]);
   struct value *tree = createTree(Arr, length);
   int QStart = 1;
   int QEnd = 4;
   struct value answer=minMax(tree, length, QStart, QEnd);
   cout<<"Minimum Value : "<<answer.minVal<<endl;
   cout<<"Maximum Value : "<<answer.maxVal;
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Minimum Value : 2
Maximum Value : 5