C++で配列の区間最小値・最大値クエリを処理する方法（セグメント木の実装）

はじめに

N個の要素を含む配列 Arr[] が与えられたとき、クエリで指定されたインデックス範囲内の最小値と最大値を求めるのが本記事の目的です。各クエリには、開始インデックス（QStart）と終了インデックス（QEnd）が与えられます。

例1

入力： Arr[] = { 1, 2, 3, 4, 5 }、QStart = 1、QEnd = 4

出力：

• 最小値：2
• 最大値：5

説明： このクエリでは、開始インデックスが1、終了インデックスが4です。この範囲内にある配列要素のうち、最小値は「2」、最大値は「5」となります。

例2

入力： Arr[] = { 10, 12, 3, 2, 5, 18 }、QStart = 2、QEnd = 5

出力：

• 最小値：2
• 最大値：18

説明： このクエリでは、開始インデックスが2、終了インデックスが5です。この範囲内にある配列要素のうち、最小値は「2」、最大値は「18」となります。

アルゴリズムの考え方

本プログラムでは、セグメント木（Segment Tree）を利用して、指定されたクエリ範囲 [lpos, rpos] 内の最小値と最大値を効率的に求めます。セグメント木を使うことで、前処理に 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) は再帰関数です。セグメント木へのポインタ root、現在ノードが担当する区間の開始インデックス startT と終了インデックス endT を引数に取ります。
• さらに、クエリ範囲の開始・終了インデックスも受け取ります。セグメント木上での現在ノードの位置が pos です。
• (qStart <= startT) かつ (qEnd >= endT) のとき、現在のノードの区間は完全にクエリ範囲に含まれるため、そのノードが持つ最小値・最大値を返します。
• 現在の区間がクエリ範囲とまったく重ならない場合は、temp の minVal と maxVal にそれぞれ初期値（9999 / -9999）を設定して返します。
• 現在の区間がクエリ範囲と部分的に重なる場合は、以下の手順で処理します。
  • 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 を担当するセグメント木を構築します。現在のノード位置は pos2 です。
• 関数 createTree(int arr0[], int num0) は、与えられた配列 arr0 からセグメント木を構築します。必要なメモリを確保したうえで、segmentTree() を呼び出して木を構成し、ルートへのポインタを返します。

サンプルコード

#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

まとめ

セグメント木を利用することで、配列の任意の区間における最小値・最大値を毎回線形探索するのではなく、クエリごとに O(log N) という高速な計算で求められるようになります。特に、同じ配列に対して多数の範囲クエリを処理する場面で大きな効果を発揮します。