【C++】バイナリインデックスツリー（BIT）で最大合計増加部分列を効率的に求める方法

この問題では、n 個の整数からなる配列 arr[] が与えられます。目的は、バイナリインデックスツリー（Binary Indexed Tree / BIT）を活用して、C++ で「最大合計増加部分列」を求めるプログラムを作成することです。

問題の概要

配列の要素を用いて、合計値が最大になる増加部分列を見つける必要があります。

増加部分列とは

現在の要素の値が、直前の位置にある要素の値よりも常に大きくなっているような部分列のことです。

バイナリインデックスツリー（BIT）とは

木構造の一種であるデータ構造で、要素の追加や更新（累積値の管理）を効率的に行うことができます。累積和や累積最大値の高速な取得に適しています。

具体例で理解しよう

入力

arr[] = {5, 1, 7, 3, 8, 2}

出力

20

解説

候補となる部分列：
{5, 7, 8} = 5 + 7 + 8 = 20
{1, 3, 8} = 1 + 3 + 8 = 12
{1, 7, 8} = 1 + 7 + 8 = 16

この中で最も合計が大きいのは {5, 7, 8} の 20 となります。

解法アプローチ

この問題では、BIT を使って達成可能な最大合計を求めます。手順は以下の通りです。

1. まず、配列の要素を map を使って座標圧縮（値の順位への変換）し、それをもとに BIT を構築します。
2. 配列の要素を先頭から順に走査します。
3. 各要素について、BIT 内で「その値より小さい要素」に関する最大合計を取得します。
4. 取得した合計に現在の要素を加えた値で BIT を更新します。
5. 最終的に、BIT 全体の中で最大の合計値を返します。

この手法により、動的計画法を素朴に実装した場合の O(n²) よりも高速な O(n log n) での処理が可能になります。

実装例

以下は、この解法の動作を示す C++ プログラムです。

#include <bits/stdc++.h>
using namespace std;
int calcMaxSum(int BITree[], int index){
    int sum = 0;
    while (index > 0) {
        sum = max(sum, BITree[index]);
        index −= index & (−index);
    }
    return sum;
}
void updateTreeVal(int BITree[], int newIndex, int index, int sumVal){
    while (index <= newIndex) {
        BITree[index] = max(sumVal, BITree[index]);
        index += index & (−index);
    }
}
int calcMaxSumBIT(int arr[], int n){
    int uniqCount = 0, maxSum;
    map<int, int> BinaryIndexTree;
    for (int i = 0; i < n; i++) {
        BinaryIndexTree[arr[i]] = 0;
    }
    for (map<int, int>::iterator it = BinaryIndexTree.begin();
    it != BinaryIndexTree.end(); it++) {
        uniqCount++;
        BinaryIndexTree[it−>first] = uniqCount;
    }
    int* BITree = new int[uniqCount + 1];
    for (int i = 0; i <= uniqCount; i++) {
        BITree[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        maxSum = calcMaxSum(BITree, BinaryIndexTree[arr[i]] − 1);
        updateTreeVal(BITree, uniqCount, BinaryIndexTree[arr[i]],
        maxSum + arr[i]);
    }
    return calcMaxSum(BITree, uniqCount);
}
int main(){
    int arr[] = {5, 1, 7, 3, 8, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The maximum sum increasing subsequence using binary
    indexed tree is "<<calcMaxSumBIT(arr, n);
    return 0;
}

実行結果

The maximum sum increasing subsequence using binary indexed tree is 20

まとめ

バイナリインデックスツリーを利用することで、最大合計増加部分列の問題を O(n log n) の計算量で効率的に解くことができます。ポイントは、map による座標圧縮で値をインデックスに対応させ、BIT で「それまでの最大合計」を高速に参照・更新する点です。同様のテクニックは、最長増加部分列（LIS）などの問題にも応用できるため、ぜひ覚えておきましょう。