จำนวนช่วงผลรวมใน C++

สมมติว่าเรามีจำนวนอาร์เรย์เป็นจำนวนเต็ม เราต้องหาจำนวนผลรวมของช่วงที่อยู่ในช่วง [ล่าง, บน] ทั้งสองอย่างรวมกัน ผลรวมของช่วง S(i, j) ถูกกำหนดเป็นผลรวมขององค์ประกอบเป็น nums จากดัชนี i ถึงดัชนี j โดยที่ i ≤ j.

ดังนั้นหากอินพุตเป็น [-3,6,-1] ต่ำกว่า =-2 และบน =2 ผลลัพธ์จะเป็น 2 เนื่องจากช่วงเป็น [0,2] ผลรวมคือ 2, [2, 2] ผลรวมคือ -2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน mergeIt() ซึ่งจะใช้คำนำหน้าอาร์เรย์ เริ่ม กลาง สิ้นสุด ล่าง บน
• i :=start, j :=mid + 1
• temp :=end - start + 1
• ต่ำ :=กลาง + 1 สูง :=กลาง + 1
• k :=0
• กำหนดอาร์เรย์ขนาด arr:ชั่วคราว
• ในขณะที่ฉัน <=กลาง ทำ −
  • ในขณะที่ (ต่ำ <=end และคำนำหน้า[ต่ำ] - คำนำหน้า[i] <ต่ำกว่า) ทำ −
    • เพิ่มขึ้นต่ำ 1
  • ในขณะที่ (สูง <=สิ้นสุดและคำนำหน้า[สูง] - คำนำหน้า[i] <=บน) ทำ −
    • เพิ่มสูง 1
  • ในขณะที่ (j <=end และ prefix[j]
  • arr[k] :=คำนำหน้า[j]
  • (เพิ่ม j ขึ้น 1)
  • (เพิ่ม k ขึ้น 1)
• arr[k] :=คำนำหน้า[i]
• (เพิ่ม i ขึ้น 1)
• (เพิ่ม k ขึ้น 1)
• นับ :=นับ + สูง - ต่ำ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int count = 0;
   void mergeIt(lli prefix[], lli start ,lli mid, lli end, lli lower, lli upper){
      lli i = start, j = mid + 1;
      lli temp = end - start + 1;
      lli low = mid + 1, high = mid + 1;
      lli k = 0;
      lli arr[temp];
      while(i <= mid){
         while(low <= end && prefix[low] - prefix[i] < lower) low++;
         while(high <= end && prefix[high] - prefix[i] <= upper) high++;
         while(j<= end && prefix[j] < prefix[i]){
            arr[k] = prefix[j];
            j++;
            k++;
         }
         arr[k] = prefix[i];
         i++;
         k++;
         count += high - low;
      }
      while(j <= end){
         arr[k] = prefix[j];
         k++;
         j++;
      }
      for(i = 0; i < temp; i++){
         prefix[start] = arr[i];
         start++;
      }
   }
   void merge(lli prefix[], lli start, lli end, lli lower, lli upper){
      if(start >= end)return;
      lli mid = start + (end - start) / 2;
      merge(prefix, start, mid, lower, upper);
      merge(prefix, mid + 1, end, lower, upper);
      mergeIt(prefix, start, mid, end, lower, upper);
   }
   int countRangeSum(vector<int>& nums, int lower, int upper) {
      lli n = nums.size();
      count = 0;
      lli prefix[n + 1];
      prefix[0] = 0;
      for(lli i = 1; i <= n; i++){
         prefix[i] = prefix[i - 1] + nums[i - 1];
      }
      merge(prefix, 0, n, lower, upper);
      return count;
   }
};
main(){
   Solution ob;
   vector<int> v = {-3,6,-1};
   cout << (ob.countRangeSum(v, -2, 2));
}

อินพุต

{-3,6,-1}
-2
2

ผลลัพธ์

2