C++で要素更新に対応する「範囲内の最大積ペア」クエリを実装する方法

この問題では、配列 arr[] と Q 個のクエリが与えられます。各クエリは次の2種類のいずれかです。

• タイプ1: 指定された範囲 [Start〜End] 内で、積が最大になるペアを見つける
• タイプ2: i 番目の要素を指定された値に更新する

本記事では、要素の更新処理を含む「範囲内の最大積ペアを求めるクエリ」を C++ で解くプログラムの作成方法を、単純な解法と効率的な解法の両面から解説します。

入出力例で問題を理解する

入力:

arr = {4, 2, 6, 9, 1}
Q = 3
Q1 = [1, 1, 4]
Q2 = [2, 2, 3]
Q3 = [1, 0, 2]

出力: 54, 12

解説

• クエリ1(タイプ1): 対象範囲は {2, 6, 9, 1}。最大積は 6 × 9 = 54
• クエリ2(タイプ2): i = 2 の要素を 3 に更新し、配列は {4, 2, 3, 9, 1} になります
• クエリ3(タイプ1): 対象範囲は {4, 2, 3}。最大積は 4 × 3 = 12

解法1:単純な全走査によるアプローチ

最もシンプルな方法は、タイプ1のクエリごとに指定範囲内のすべてのペアの積を計算し、その中から最大値を求めるものです。

サンプルコード

#include <iostream>
using namespace std;
int max(int a, int b){
    if(a>b)
        return a;
    return b;
}
int findMaxProductPair(int arr[], int n, int start, int end){
    int maxProd = 0;
    for(int i = start; i <= end; i++){
        for(int j = i+1; j <= end; j++){
            maxProd = max(maxProd, (arr[i]*arr[j]));
        }
    }
    return maxProd;
}
int main(){
    int arr[] = {4, 2, 6, 9, 1, 5};
    int n = 6;
    int Q = 3;
    int query[Q][3] = {{1, 1, 4}, {2, 2, 3}, {1, 0, 2}};
    for(int i = 0; i < Q; i++){
        if(query[i][0] == 1){
            cout<<"The maximum product pair in the range is "<<findMaxProductPair(arr, n, query[i][1], query[i][2])<<"\n";
        }
        else if(query[i][0] == 2){
            cout<<"Updating values...\n";
            arr[query[i][1]] = query[i][2];
        }
    }
    return 0;
}

実行結果

The maximum product pair in the range is 54
Updating values...
The maximum product pair in the range is 12

このアプローチは正しく動作しますが、クエリごとに範囲内の全ペアを調べる必要があるため、時間計算量は O(N²) になります。また、初期値を 0 としているため、配列がすべて負の数の場合には正しい結果が得られない点にも注意が必要です。

解法2:セグメント木による効率的なアプローチ

より効率的な解決策として、セグメント木(segment tree)というデータ構造を使用する方法があります。各区間のノードに「最大値(maxEle)」と「2番目に大きい値(secMax)」を保持しておき、タイプ1のクエリに対してはこの2つの積を返します。

この方法を使えば、クエリ処理・更新処理ともに O(log N) で実行できるため、配列が大きくクエリが多数発生する場合でも高速に動作します。

サンプルコード

#include <iostream>
using namespace std;
struct segment {
    int maxEle;
    int secMax;
};
segment findMaxProductPair(segment* prodTree, int index, int start, int end, int L, int R) {
    segment result;
    result.maxEle = -1;
    result.secMax = -1;
    if (L > end || R < start || start > end)
        return result;
    if (start >= L && end <= R)
        return prodTree[index];
    int middleIndex = (start + end) / 2;
    segment left = findMaxProductPair(prodTree, 2 * index, start, middleIndex, L, R);
    segment right = findMaxProductPair(prodTree, 2 * index + 1, middleIndex + 1, end, L, R);
    result.maxEle = max(left.maxEle, right.maxEle);
    result.secMax = min(max(left.maxEle, right.secMax), max(right.maxEle, left.secMax));
    return result;
}
void update(segment* prodTree, int index, int start, int end, int i, int updateVal) {
    if (i < start || i > end)
        return;
    if (start == end) {
        prodTree[index].maxEle = updateVal;
        prodTree[index].secMax = -1;
        return;
    }
    int middleIndex = (start + end) / 2;
    update(prodTree, 2 * index, start, middleIndex, i, updateVal);
    update(prodTree, 2 * index + 1, middleIndex + 1, end, i, updateVal);
    prodTree[index].maxEle = max(prodTree[2 * index].maxEle, prodTree[2 * index + 1].maxEle);
    prodTree[index].secMax = min(max(prodTree[2 * index].maxEle, prodTree[2 * index + 1].secMax), max(prodTree[2 * index + 1].maxEle, prodTree[2 * index].secMax));
}
void buildtree(segment* prodTree, int* arr, int index, int start, int end) {
    if (start > end) {
        return;
    }
    if (start == end) {
        prodTree[index].maxEle = arr[start];
        prodTree[index].secMax = -1;
        return;
    }
    int middleIndex = (start + end) / 2;
    buildtree(prodTree, arr, 2 * index, start, middleIndex);
    buildtree(prodTree, arr, 2 * index + 1, middleIndex + 1, end);
    int maximum = max(prodTree[2 * index].maxEle, prodTree[2 * index + 1].maxEle);
    int secMaximum = min(max(prodTree[2 * index].maxEle, prodTree[2 * index + 1].secMax), max(prodTree[2 * index + 1].maxEle, prodTree[2 * index].secMax));
    prodTree[index].maxEle = maximum;
    prodTree[index].secMax = secMaximum;
}
int main() {
    int arr[] = {4, 2, 6, 9, 1, 5};
    int n = 6;
    int Q = 3;
    segment* prodTree = new segment[4 * n + 1];
    buildtree(prodTree, arr, 1, 0, n - 1);
    int query[Q][3] = {{1, 1, 4}, {2, 2, 3}, {1, 0, 2}};
    for(int i = 0; i < Q; i++){
        if(query[i][0] == 1){
            segment result = findMaxProductPair(prodTree, 1, 0, n - 1, query[i][1], query[i][2]);
            cout<<"The maximum product pair in the range is "<<(result.maxEle*result.secMax)<<"\n";
        }
        else if(query[i][0] == 2){
            cout<<"Updating values...\n";
            update(prodTree, 1, 0, n - 1, query[i][1], query[i][2]);
        }
    }
    return 0;
}

実行結果

The maximum product pair in the range is 54
Updating values...
The maximum product pair in the range is 12

まとめ

範囲内の最大積ペアを求めるクエリは、単純な全走査では O(N²) の計算量が必要になりますが、セグメント木を使えば各ノードに最大値と2番目に大きい値を格納することで、クエリ・更新ともに O(log N) で処理できます。要素の更新を伴う区間クエリを高速に扱いたい場合、セグメント木は非常に有効な選択肢となります。