C++を使用した更新なしの範囲合計クエリ

この記事では、整数になるサイズnの配列を提供します。次に、インデックスLからインデックスRまでの要素の合計を計算し、クエリを複数回実行するか、[L、R]から指定された範囲の合計を計算する必要があります。例-

Input : arr[] = {1, 2, 3, 4, 5}
   L = 1, R = 3
   L = 2, R = 4
Output : 9
   12

Input : arr[] = {1, 2, 3, 4, 5}
   L = 0, R = 4
   L = 1, R = 2
Output : 15
   5

解決策を見つけるためのアプローチ

この質問には2つの解決策があります。 1つ目は、ブルートフォースアプローチとプレフィックス合計（効率的）アプローチによるものです。

ブルートフォースアプローチ

このアプローチでは、指定された範囲をトラバースして合計を出力します。

例

#include<bits/stdc++.h>

using namespace std;

int main() {
   int arr[] = {1, 2, 3, 4, 5};
   int n = sizeof(arr)/sizeof(int); // size of given array.
   int L1 = 1, R1 = 3;
   int L2 = 2, R2 = 4;
   int sum = 0;
   for(int i = L1; i <= R1; i++) // traversing through the first range.
      sum += arr[i];
   cout << sum << "\n";
   sum = 0;
   for(int i = L2; i <= R2; i++) // traversing through the second range.
      sum += arr[i];
   cout << sum << "\n";
}

出力

9
12

上記のコードの説明

このアプローチでは、指定された範囲を単純にトラバースします。この場合、このプログラムは検索時間計算量O（N）を持っているので優れています。ここで、Nは指定された配列のサイズです。それでも、複数のクエリQが与えられると、これは変化し、複雑さはO（N * Q）に変わります。ここで、Qはクエリの数、Nは指定された配列のサイズです。残念ながら、今回の複雑さはより高い制約を処理できないため、今度はより高い制約に対して機能する効率的なアプローチを検討します。

効率的なアプローチ

このアプローチでは、prefixの合計配列となるprefixという名前の新しい配列を作成し、指定された範囲の合計に答えます。

例

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

int main() {
   int arr[] = {1, 2, 3, 4, 5};
   int n = sizeof(arr)/sizeof(int); // size of given array.
   int L1 = 1, R1 = 3;
   int L2 = 2, R2 = 4;
   int sum = 0;
   int prefix[n];
   for(int i = 0; i < n; i++){
      sum += arr[i];
      prefix[i] = sum;
   }

   if(L1) // to avoid segmentation fault
      cout << prefix[R1] - prefix[L1 - 1] << "\n";
   else
      cout << prefix[R1] << "\n";

   if(L2) // avoiding segmentation fault.
      cout << prefix[R2] - prefix[L2 - 1] << "\n";
   else
      cout << prefix[R2] << "\n";
}

出力

9
12

上記のコードの説明

このアプローチでは、プレフィックスの合計値をプレフィックスと呼ばれる配列に格納します。さて、この配列はプログラムを非常に効率的にします。これにより、O（1）の検索時間計算量が得られます。これは、取得できる最高の複雑さです。したがって、Q量のクエリが与えられると、検索時間計算量はO（ Q）ここで、Qはクエリの数です。

結論

この記事では、Prefix合計配列を使用して、更新なしで範囲合計クエリを見つける問題を解決します。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（通常および効率的）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。この記事がお役に立てば幸いです。