C++でBinary Indexed Tree（BIT）を使って最大和増加部分列を求める方法

この記事では、N個の要素からなる配列 arr[] が与えられたとき、C++のBinary Indexed Tree（BIT、フェニック木）を活用して、最大和増加部分列（Maximum Sum Increasing Subsequence）を求めるプログラムの作成方法を解説します。

問題例で理解しよう

入力

arr[] = {4, 1, 9, 2, 3, 7}

出力

13

解説

この場合、最大の和を持つ増加部分列は「1, 2, 3, 7」であり、その合計は 1 + 2 + 3 + 7 = 13 となります。

解法のアプローチ

この問題を効率的に解くために、Binary Indexed Tree（BIT）を使用します。基本的な考え方は以下の通りです。

手順1： 配列の各値を座標圧縮（値のランク付け）し、BITのインデックスにマッピングします。

手順2： 配列を左から順に走査し、各要素について「その要素より小さい値で終わる増加部分列の最大和」をBITから取得します。

手順3： 取得した最大和に現在の要素の値を加えたものを、BITの該当位置に更新（max演算）していきます。

通常の動的計画法（DP）では O(N²) の計算量が必要ですが、BITを用いることで O(N log N) まで計算量を削減できます。

C++実装例

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

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

// indexまでの範囲から最大の和を取得する関数
int calcMaxSum(int BITree[], int index){
    int maxSum = 0;
    while (index > 0){
        maxSum = max(maxSum, BITree[index]);
        index -= index & (-index);
    }
    return maxSum;
}

// BITを更新する関数（最大値で更新）
void updateBIT(int BITree[], int newIndex, int index, int val){
    while (index <= newIndex){
        BITree[index] = max(val, BITree[index]);
        index += index & (-index);
    }
}

// 最大和増加部分列を求めるメイン関数
int maxSumIS(int arr[], int n){
    int index = 0, maxSum;
    map<int, int> arrMap;
    
    // 座標圧縮：値をBITのインデックスにマッピング
    for (int i = 0; i < n; i++){
        arrMap[arr[i]] = 0;
    }
    for (map<int, int>::iterator it = arrMap.begin(); it != arrMap.end(); it++){
        index++;
        arrMap[it->first] = index;
    }
    
    int* BITree = new int[index + 1];
    for (int i = 0; i <= index; i++){
        BITree[i] = 0;
    }
    
    // 各要素について最大和を計算し、BITを更新
    for (int i = 0; i < n; i++){
        maxSum = calcMaxSum(BITree, arrMap[arr[i]] - 1);
        updateBIT(BITree, index, arrMap[arr[i]], maxSum + arr[i]);
    }
    
    return calcMaxSum(BITree, index);
}

int main() {
    int arr[] = {4, 6, 1, 9, 2, 3, 5, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Binary Indexed Treeを用いた最大和増加部分列の和: " << maxSumIS(arr, n);
    return 0;
}

出力

Binary Indexed Treeを用いた最大和増加部分列の和: 19

コードのポイント

この実装における重要なポイントを整理します。

calcMaxSum関数： BITの特性を利用して、指定したインデックスまでの範囲に含まれる最大の部分列和を O(log N) で取得します。インデックスの最下位ビットを減算しながら親ノードを辿っていくのがポイントです。

updateBIT関数： 値を更新する際、通常のBITのように加算するのではなく、max演算で更新します。これにより、各区間の最大和が常に正しく保持されます。

座標圧縮： 配列の値をそのままBITのインデックスに使うと、値の範囲が大きい場合にメモリを無駄に消費します。mapを使って値を1から連番に圧縮することで、配列サイズを要素数 N に抑えられます。

まとめ

Binary Indexed Treeを応用することで、最大和増加部分列の問題を O(N log N) の時間計算量で効率的に解くことができます。BITは区間和の計算でよく知られていますが、このようにmax演算と組み合わせることで、さまざまな最適化問題にも応用できる強力なデータ構造です。競技プログラミングでも頻出のテクニックなので、ぜひマスターしておきましょう。