C++で指定範囲内の最大部分配列和を求める方法｜セグメント木による実装

任意のサイズの整数要素からなる配列が与えられます。この記事では、指定された範囲（first〜last）内で、配列の任意のインデックスから始まる連続した部分配列の中から、合計値が最大になるものを求める方法を解説します。

この種の問題はセグメント木（Segment Tree）を使うことで効率的に解けます。各ノードに「区間の合計」「左端から伸びる最大和」「右端で終わる最大和」「区間内の最大部分配列和」の4つの情報を持たせることで、範囲クエリに対して O(log N) で答えを取得できます。

入出力シナリオの例

入力 − int arr[] = { 3, 2, -1, 6, 7, 2 }, int first = 0, int last = 5

出力 − 指定範囲における最大部分配列和：19

説明 − 正と負の値が混在する配列に対して、0番目から5番目まで（配列全体）の範囲が指定されています。この場合、配列全体を取った 3 + 2 + (-1) + 6 + 7 + 2 = 19 が最大の合計となります。

入力 − int arr[] = {-2, 1, 3, 4, 8, 9, 23}, int first = 0, int last = 3

出力 − 指定範囲における最大部分配列和：8

説明 − 0番目から3番目までの範囲が指定されています。先頭の -2 を含めると合計が下がってしまうため、1 + 3 + 4 = 8 を選ぶのが最適です。

プログラムで使用しているアプローチ

• 木構造用の構造体を作成し、max_val（右側と接続したときの最大和）、max_temp（左側と接続したときの最大和）、total（区間の合計）、sub_sum（区間内の最大部分配列和）をメンバ変数として持ちます。デフォルトコンストラクタで各メンバを十分に小さい値（-MAX）で初期化します。
• set_nodes メソッドを作成します。左右の子ノードを統合して親ノードを生成するメソッドで、次のように計算します。
  ・max_val = max(left.max_val, left.total + right.max_val)
  ・max_temp = max(right.max_temp, right.total + left.max_temp)
  ・total = left.total + right.total
  ・sub_sum = max({left.sub_sum, right.sub_sum, left.max_temp + right.max_val})
  計算後、ノードを返します。
• build_tree メソッドを作成し、木を構築します。
  • first == last の場合（葉ノード）、total・max_temp・max_val・sub_sum をすべて arr[first] に設定して返します。
  • それ以外の場合は、build_tree(node, arr, first, temp, 2 * inx) と build_tree(node, arr, temp + 1, last, 2 * inx + 1) を再帰的に呼び出し、node[inx] = set_nodes(node[2 * inx], node[2 * inx + 1]) で親ノードを更新します。
• create_tree メソッドを作成します。temp = (int)(ceil(log2(size))) として必要なノード数を算出し、build_tree() に木のノード配列、arr、0、size - 1、1 を引数として渡して呼び出します。
• 最大部分配列和を問い合わせるメソッド maximum_sub(Tree* node, int temp, int temp_2, int temp_3, int temp_4, int inx) を作成します。
  • temp > temp_4 または temp_2 < temp_3 の場合（範囲外）、初期化された空ノードを返します。
  • temp >= temp_3 かつ temp_2 <= temp_4 の場合（現在の区間が完全に範囲内）、node[inx] をそのまま返します。
  • そうでなければ、left = maximum_sub(node, temp, mid, temp_3, temp_4, 2 * inx)、right = maximum_sub(node, mid + 1, temp_2, temp_3, temp_4, 2 * inx + 1) を再帰的に呼び出します。
  • result = set_nodes(left, right) として左右の結果を統合し、result を返します。
• maximum_subarray(Tree* node, int first, int last, int size) メソッドを作成します。
  • maximum_sub(node, 0, size - 1, first, last, 1) を呼び出します。
  • temp.sub_sum を返します。
• main() 関数では次の処理を行います。
  • 正負の値を含む整数型の配列を宣言し、配列のサイズを計算します。
  • 先頭インデックスから末尾インデックスまでの範囲を定義します。
  • maximum_subarray(node, first, last, size) を呼び出して、指定範囲内の最大部分配列和を計算し、結果を出力します。

コード例

#include <bits/stdc++.h>
using namespace std;
#define MAX 0x3f3f
struct Tree{
    int max_val;
    int max_temp;
    int total;
    int sub_sum;
    Tree(){
        max_val = max_temp = sub_sum = -MAX;
        total = -MAX;
    }
};

Tree set_nodes(Tree left, Tree right){
    Tree node;
    node.max_val = max(left.max_val, left.total + right.max_val);
    node.max_temp = max(right.max_temp, right.total + left.max_temp);
    node.total = left.total + right.total;
    node.sub_sum = max({left.sub_sum, right.sub_sum, left.max_temp + right.max_val});
    return node;
}
void build_tree(Tree* node, int arr[], int first, int last, int inx){
    if(first == last){
        node[inx].total = arr[first];
        node[inx].max_temp = arr[first];
        node[inx].max_val = arr[first];
        node[inx].sub_sum = arr[first];
        return;
    }
    int temp = (first + last) / 2;
    build_tree(node, arr, first, temp, 2 * inx);
    build_tree(node, arr, temp + 1, last, 2 * inx + 1);
    node[inx] = set_nodes(node[2 * inx], node[2 * inx + 1]);
}
Tree* create_tree(int arr[], int size){
    int temp = (int)(ceil(log2(size)));
    int n = 2 * (int)pow(2, temp) - 1;
    Tree* node = new Tree[n];
    build_tree(node, arr, 0, size - 1, 1);
    return node;
}
Tree maximum_sub(Tree* node, int temp, int temp_2, int temp_3, int temp_4, int inx){
    if(temp > temp_4 || temp_2 < temp_3){
        Tree nullNode;
        return nullNode;
    }
    if(temp >= temp_3 && temp_2 <= temp_4){
        return node[inx];
    }
    int mid = (temp + temp_2) / 2;
    Tree left = maximum_sub(node, temp, mid, temp_3, temp_4, 2 * inx);
    Tree right = maximum_sub(node, mid + 1, temp_2, temp_3, temp_4, 2 * inx + 1);
    Tree result = set_nodes(left, right);
    return result;
}
int maximum_subarray(Tree* node, int first, int last, int size){
    Tree temp = maximum_sub(node, 0, size - 1, first, last, 1);
    return temp.sub_sum;
}
int main(){
   int arr[] = { 3, 2, -1, 6, 7, 2 };
   int size = sizeof(arr) / sizeof(arr[0]);
   Tree* node = create_tree(arr, size);
   int first = 0;
   int last = 5;
   int sub_sum = maximum_subarray(node, first, last, size);
   cout<< "Maximum Subarray Sum in a given Range is: "<< sub_sum;
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

Maximum Subarray Sum in a given Range is: 19

この実装では、木の構築に O(N)、各範囲クエリの処理に O(log N) の計算量で最大部分配列和を求められます。配列の要素更新が行われる場合や、同じ配列に対して何度も異なる範囲のクエリを実行する場面で、特に威力を発揮する手法です。