Range Sum Queries โดยไม่มีการอัปเดตโดยใช้ 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

แนวทางในการหาทางออก

มีสองวิธีแก้ไขปัญหานี้ วิธีแรกคือโดยวิธี Brute Force และวิธี Prefix sum (ประสิทธิภาพ)

แนวทางกำลังเดรัจฉาน

ในแนวทางนี้ เราจะข้ามผ่านช่วงที่กำหนดและพิมพ์ผลรวม

ตัวอย่าง

#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 ซึ่งจะเป็นคำนำหน้า sum array จากนั้นเราจะตอบผลรวมของช่วงที่กำหนด

ตัวอย่าง

#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 คือจำนวนการสืบค้น

บทสรุป

ในบทความนี้ เราแก้ปัญหาเพื่อค้นหาคิวรีผลรวมของช่วงโดยไม่มีการอัปเดตโดยใช้อาร์เรย์ผลรวมคำนำหน้า นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal และ มีประสิทธิภาพ ) โดยที่เราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ หวังว่าบทความนี้จะเป็นประโยชน์