C++でバイナリリフティングを使って累積和からX以上となる最初の要素を見つける方法

この問題では、N個の数値からなる配列arr[]と整数xが与えられます。求められているのは、バイナリリフティング（Binary Lifting）を使用して、N個の数値の累積和（プレフィックスサム）の中からX以上となる最初の要素を見つけるプログラムを作成することです。

配列の累積和（Prefix Sum）とは、元の配列の先頭から各インデックスまでの要素の合計を、その位置の値とする配列のことです。

例：array[] = {5, 2, 9, 4, 1}

prefixSumArray[] = {5, 7, 16, 20, 21}

問題を理解するための例

入力：arr[] = {5, 2, 9, 4, 1}, X = 19
出力：3

解法のアプローチ

ここでは、バイナリリフティングという概念を用いてこの問題を解きます。バイナリリフティングとは、0からNまでの範囲で、対象の数値に2のべき乗を加算していく（ビットの反転によって実現する）手法です。

二分木におけるリフティングの考え方と同様に、まずインデックス「P」の初期値を決定します。これは、累積和がXを超えない範囲でビットを反転しながら値を増加させていくことで求めます。その後、この位置「P」を基準としてリフトを行います。

具体的には、i番目のビットを反転しても合計がXを超えないようなビットから順に反転していきます。このとき、「P」の値に応じて次の2つの場合が考えられます。

1つ目は、i番目のリフトによって値が増加した場合、目標位置が「position + 2^i」と「position + 2^(i+1)」の間にあるケース。2つ目は、目標位置が「position」と「position + 2^i」の間にあるケースです。

この仕組みを利用することで、条件を満たすインデックス位置を効率的に特定できます。

実装例

ソリューションの動作を示すプログラム

#include <iostream>
#include <math.h>
using namespace std;
void generatePrefixSum(int arr[], int prefSum[], int n){
   prefSum[0] = arr[0];
   for (int i = 1; i < n; i++)
      prefSum[i] = prefSum[i - 1] + arr[i];
}
int findPreSumIndexBL(int prefSum[], int n, int x){
   int P = 0;
   int LOGN = log2(n);
   if (x <= prefSum[0])
      return 0;
   for (int i = LOGN; i >= 0; i--) {
      if (P + (1 << i) < n &&
         prefSum[P + (1 << i)] < x) {
         P += (1 << i);
      }
   }
   return P + 1;
}
int main(){
   int arr[] = { 5, 2, 9, 4, 1 };
   int X = 19;
   int n = sizeof(arr) / sizeof(arr[0]);
   int prefSum[n] = { 0 };
   generatePrefixSum(arr, prefSum, n);
   cout<<"与えられた数以上となる最初の要素のインデックスは ";
   cout<<findPreSumIndexBL(prefSum, n, X);
   return 0;
}

出力

与えられた数以上となる最初の要素のインデックスは 3

計算量

時間計算量：O(log n) ― ビット反転による探索ループは最大でもlog₂(n)回しか実行されないため、線形探索（O(n)）よりも高速です。

空間計算量：O(n) ― 累積和を格納するための補助配列が必要です。