C++で指定範囲の最大プレフィックス合計（接頭辞和）を求める方法

問題文

n個の整数からなる配列とq個のクエリが与えられます。各クエリはlからrまでの範囲を指定するもので、それぞれのクエリに対して、範囲l～rにおける最大の接頭辞和（プレフィックス合計）を求めてください。

例

入力配列が arr[] = {-1, 2, 3, -5} の場合、
クエリ数 = 2 で、範囲は次の通りです。
l = 0, r = 3
l = 1, r = 3
このとき出力は 4 と 5 になります。

• 1つ目のクエリの範囲(0, 3)は [-1, 2, 3, -5] を指します。接頭辞（先頭から連続する要素の和）として扱うため、必ず -1 から始める必要があります。したがって、最大接頭辞和は -1 + 2 + 3 = 4 となります。
• 2つ目のクエリの範囲(1, 3)は [2, 3, -5] を指します。こちらも先頭の 2 から始まるため、最大接頭辞和は 2 + 3 = 5 となります。

アルゴリズム

• 各ノードに「区間の総和（sum）」と「接頭辞和（prefix_sum）」の2つの値を持たせたセグメント木を構築し、その上で範囲クエリを実行することで最大接頭辞和を求めます。
• 最大接頭辞和を求めるためには、「区間の総和」と「接頭辞和」という2つの情報が必要になります。
• マージ（統合）処理では、区間の総和と、max(左側の接頭辞和, 左側の総和 + 右側の接頭辞和) として計算される接頭辞和の2つの値を返します。
• 2つの区間を結合したときの最大接頭辞和は、「左側のみの接頭辞和」または「左側の総和 + 右側の接頭辞和」のいずれか大きい方となります。

この手法では、セグメント木の構築に O(n) の計算量を要しますが、構築後の各クエリは O(log n) で処理できるため、多数の範囲クエリを効率的に扱えます。

実装例（C++コード）

#include <bits/stdc++.h>
using namespace std;
typedef struct node {
    int sum;
    int prefix;
} node;
node tree[4 * 10000];
void build(int *arr, int idx, int start, int end) {
    if (start == end) {
        tree[idx].sum = arr[start];
        tree[idx].prefix = arr[start];
    } else {
        int mid = (start + end) / 2;
        build(arr, 2 * idx + 1, start, mid);
        build(arr, 2 * idx + 2, mid + 1, end);
        tree[idx].sum = tree[2 * idx + 1].sum + tree[2 *
        idx + 2].sum;
        tree[idx].prefix = max(tree[2 * idx + 1].prefix,
        tree[2 * idx + 1].sum + tree[2 * idx + 2].prefix);
    }
}
node query(int idx, int start, int end, int l, int r) {
    node result;
    result.sum = result.prefix = -1;
    if (start > r || end < l) {
        return result;
    }
    if (start >= l && end <= r) {
        return tree[idx];
    }
    int mid = (start + end) / 2;
    if (l > mid) {
        return query(2 * idx + 2, mid + 1, end, l, r);
    }
    if (r <= mid) {
        return query(2 * idx + 1, start, mid, l, r);
    }
    node left = query(2 * idx + 1, start, mid, l, r);
    node right = query(2 * idx + 2, mid + 1, end, l, r);
    result.sum = left.sum + right.sum;
    result.prefix = max(left.prefix, left.sum + right.prefix);
    return result;
}
int main() {
    int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    build(arr, 0, 0, n - 1);
    cout << "Result = " << query(0, 0, n - 1, 3, 5).prefix
    << endl;
    return 0;
}

出力結果

上記プログラムをコンパイルして実行すると、以下の出力が得られます。

Result = -1

出力の解説

この例では、配列 {-2, -3, 4, -1, -2, 1, 5, -3} のインデックス3～5、すなわち値 {-1, -2, 1} を範囲としてクエリを実行しています。接頭辞和は先頭から順に -1 → -3 → -2 と変化するため、その最大値である -1 が出力されます。