Translate the following using C++: Interval sum query without updates

In this article, we will be given an array of size n, which is an integer. We will then calculate the sum of elements from index L to index R and perform multiple queries, or we need to calculate the sum of the given range [L, R]. For example -

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

Methods to find solution

There are two solutions to this problem. The first is through brute force methods and prefix sum (efficient) methods.

Brute Force Method

In this method we will iterate over the given range and print out the sum.

Example

#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";
}

Output

9
12

Explanation of the above code

In this method, we just iterate over the given range; in this case Next, this program is good because its search time complexity is O(N), where N is the size of the given array. Nonetheless, things change when we are given multiple queries Q, then our complexity becomes O(N*Q), where Q is the number of queries and N is the size of the given array. Unfortunately, this time complexity cannot handle higher constraints, so now we will look at an efficient method for higher constraints.

Efficient method

In this method we will create a new array called prefix which will serve as our prefix and array and then we answer the sum of the given range.

Example

#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";
}

Output

9
12

Explanation of the above code

In this method, we store the prefix and value in a file called prefix in the array. Now, this array makes our program very efficient because it gives us a search time complexity of O(1), which is the best complexity you can get, so when we are given Q queries, we The search time complexity becomes O(Q), where Q is the number of queries.

Conclusion

In this article, we solved a problem of finding ranges and queries without updates using prefixes and arrays. We also learned a C program for this problem and a complete solution (common and efficient). We can write the same program in other languages ​​like C, Java, Python and others. Hope you found this article helpful.

The above is the detailed content of Translate the following using C++: Interval sum query without updates. For more information, please follow other related articles on the PHP Chinese website!