【C++】L番目に小さい値とR番目に小さい値の絶対差を返すクエリを実装する方法

このチュートリアルでは、配列内の「L番目に小さい値」と「R番目に小さい値」のインデックスの絶対差を求めるクエリ処理について解説します。

整数からなる配列とQ個のクエリが与えられます。各クエリは2つの整数L・Rから構成され、元の配列におけるL番目に小さい値とR番目に小さい値のインデックスの絶対差を計算して出力するのが課題です。

問題のポイント

ここで求めるのは「値同士の差」ではなく、それぞれの値が元の配列のどこに位置していたかという「インデックスの差」である点に注意してください。

例として、配列 arr = {1, 7, 4, 2, 8} を値の昇順に並べると次のようになります。

1（インデックス0）→ 2（インデックス3）→ 4（インデックス2）→ 7（インデックス1）→ 8（インデックス4）

この状態でクエリ (L=2, R=4) が与えられた場合、2番目に小さい値「2」のインデックスは3、4番目に小さい値「7」のインデックスは1なので、答えは |3 − 1| = 2 となります。

アルゴリズムの手順

1. 配列の各要素を「値」と「元のインデックス」のペア（pair）として新しい配列に格納します。
2. ペアの配列を値を基準に昇順ソートします。これにより、k番目の要素が「k番目に小さい値」とその元のインデックスを保持するようになります。
3. 各クエリ (L, R) ごとに、ソート後のL番目とR番目の要素が持つ元のインデックスの絶対差を計算して出力します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;

// クエリに対する結果を返す関数
int respondingQuery(pair<int, int> arr[], int l, int r) {
    int result = abs(arr[l - 1].second - arr[r - 1].second);
    return result;
}

// すべてのクエリを処理する関数
void calcDifference(int givenarr[], int a, int q[][2], int b) {
    pair<int, int> arr[a];
    for (int i = 0; i < a; i++) {
        arr[i].first = givenarr[i];
        arr[i].second = i;
    }
    sort(arr, arr + a);
    for (int i = 0; i < b; i++)
        cout << respondingQuery(arr, q[i][0], q[i][1]) << endl;
}

int main() {
    int arr[] = { 1, 7, 4, 2, 8 };
    int arraySize = sizeof(arr) / sizeof(arr[0]);
    int query[][2] = { { 2, 4 }, { 1, 5 }, { 3, 5 }, { 1, 3 } };
    int querySize = sizeof(query) / sizeof(query[0]);
    calcDifference(arr, arraySize, query, querySize);
    return 0;
}

出力結果

2
4
2
2

コードの解説

respondingQuery() は、ソート済みのペア配列を受け取り、L番目とR番目の要素に保存された元のインデックス（second）の差の絶対値を返す関数です。

calcDifference() は、元の配列を (値, インデックス) のペアの列に変換してソートし、その後すべてのクエリを順番に処理して結果を標準出力に表示します。なお、クエリで指定するL・Rは配列の要素数以内である必要があります。

計算量

ソートに O(N log N)、各クエリへの回答には O(1) しかかからないため、全体の計算量は O(N log N + Q) となります。クエリの数が多い場合でも高速に動作するのがこの手法の大きな利点です。