सी++ प्रोग्राम बिना अपडेट के रेंज सम क्वेश्चन के लिए?

यहां हम देखेंगे कि किसी सरणी में अनुक्रमणिका i से अनुक्रमणिका j तक के तत्वों का योग कैसे प्राप्त करें। यह मूल रूप से रेंज क्वेरी है। इंडेक्स i से j तक केवल एक लूप चलाकर और योग की गणना करके कार्य आसान है। लेकिन हमें इस बात का ध्यान रखना होगा कि इस तरह की रेंज क्वेरी को कई बार निष्पादित किया जाएगा। इसलिए यदि हम बताई गई विधि का उपयोग करते हैं, तो इसमें अधिक समय लगेगा। अधिक कुशल तरीके से इस समस्या को हल करने के लिए हम पहले संचयी योग प्राप्त कर सकते हैं, फिर सीमा योग निरंतर समय में पाया जा सकता है। आइए विचार प्राप्त करने के लिए एल्गोरिथम देखें।

एल्गोरिदम

rangeSum(arr, i, j)

begin
   c_arr := cumulative sum of arr
   if i = 0, then
      return c_arr[j];
      return c_arr[j] – c_arr[i-1]
end

उदाहरण

#include<iostream>
using namespace std;
void cumulativeSum(int c_arr[], int arr[], int n){
   c_arr[0] = arr[0];
   for(int i = 1; i<n; i++){
      c_arr[i] = arr[i] + c_arr[i-1];
   }
}
int rangeSum(int c_arr[], int i, int j){
   if( i == 0){
      return c_arr[j];
   }
   return c_arr[j] - c_arr[i-1];
}
main() {
   int data[] = {5, 4, 32, 8, 74, 14, 23, 65};
   int n = sizeof(data)/sizeof(data[0]);
   int c_arr[n];
   cumulativeSum(c_arr, data, n); //get cumulative sum
   cout << "Range sum from index (2 to 5): " << rangeSum(c_arr, 2, 5) << endl;
   cout << "Range sum from index (0 to 3): " << rangeSum(c_arr, 0, 3) << endl;
   cout << "Range sum from index (4 to 7): " << rangeSum(c_arr, 4, 7) << endl;
}

आउटपुट

Range sum from index (2 to 5): 128
Range sum from index (0 to 3): 49
Range sum from index (4 to 7): 176