C++でバイナリリフティングを使用したN個の数値のプレフィックス合計のX以上の最初の要素

この問題では、N個の数値と整数値xで構成される配列arr[]が与えられます。私たちのタスクは、バイナリリフティングを使用して、N個の数値のプレフィックス合計からX以上の最初の要素を見つけるためのプログラムを作成することです。 。

プレフィックス合計 配列の要素の数は、各要素が最初の配列のそのインデックスまでのすべての要素の合計である配列です。

例-array[]={5、2、9、4、1}

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

問題を理解するために例を見てみましょう

Input: arr[] = {5, 2, 9, 4, 1}, X = 19
Output: 3

ソリューションアプローチ

ここでは、バイナリリフティングの概念を使用して問題を解決します。 。バイナリリフティングは、0からNの範囲で2の累乗（ビットを反転することによって実行）で指定された数値の値を増やしています。

'P'インデックスの初期値を見つける二分木を持ち上げるのと同様の概念を検討します。これは、値がXより大きくないことを確認するためにビットを反転することによって増加します。ここで、この位置「P」とともにリフトを検討します。

このために、i番目のビットの反転によって合計がXより大きくならないように、数値のビットの反転を開始します。ここで、「P」の値に基づいて2つのケースがあります-

目標位置が'位置+2^ iの間にある 'および'位置+2^（i + 1） 'i番目のリフトが値を増加させた場所。または、ターゲット位置が'位置の間にあります 'および'位置+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<<"The index of first elements of the array greater than the given number is ";
   cout<<findPreSumIndexBL(prefSum, n, X);
   return 0;
}

出力

The index of first elements of the array greater than the given number is 3