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 と呼ばれる新しい配列を作成し、指定された範囲の合計を返します。

例

#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

上記のコードの説明

このメソッドでは、プレフィックスと値を prefix という名前のファイルに保存します。配列。さて、この配列により、検索時間の複雑さが O(1) になるため、プログラムは非常に効率的になります。これは、得られる最高の複雑さです。そのため、Q 個のクエリが与えられると、検索時間の複雑さは O(Q) になります。ここで、Q はクエリの数です。

結論

この記事では、プレフィックスと配列を使用して更新なしで範囲とクエリを検索する問題を解決しました。また、この問題に対する C プログラムと完全な解決策 (一般的で効率的な) も学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ を使用して以下を翻訳します: 更新なしの間隔合計クエリの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。