C++-এ Range Addition: অ্যারে রেঞ্জ আপডেট দিয়ে মডিফাইড অ্যারে বের করা

আমাদের একটি সাইজ n এর অ্যারে আছে যা শূন্য দিয়ে ইনিশিয়ালাইজড। এছাড়া k সংখ্যক আপডেট অপারেশন আছে। প্রতিটি অপারেশন একটি ট্রিপলেট: [startIndex, endIndex, inc] যা সাব-অ্যারে A[startIndex ... endIndex] (শুরু এবং শেষ ইনডেক্সই ইনক্লুসিভ) এর প্রতিটি এলিমেন্টকে inc দিয়ে ইনক্রিমেন্ট করে। সমস্ত k অপারেশন এক্সিকিউট হওয়ার পর মডিফাইড অ্যারে বের করতে হবে।

উদাহরণ

ইনপুট: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]

আউটপুট: [-2, 0, 3, 5, 3]

সমাধানের পদ্ধতি (Difference Array / Prefix Sum Technique)

প্রতিটি আপডেটকে O(1) তে হ্যান্ডেল করার জন্য ডিফারেন্স অ্যারে টেকনিক ব্যবহার করা হয়। ধাপগুলো:

1. সাইজ n এর একটি রেজাল্ট অ্যারে ret তৈরি করুন (শূন্য দিয়ে ইনিশিয়ালাইজড)।
2. প্রতিটি আপডেট [l, r, val] এর জন্য:
   • ret[l] += val
   • যদি r + 1 < n হয়, তবে ret[r + 1] -= val
3. প্রিফিক্স সাম করুন: for i = 1 to n-1: ret[i] += ret[i-1]
4. ret রিটার্ন করুন।

এই পদ্ধতিতে টাইম কমপ্লেক্সিটি O(n + k) যা খুব দক্ষ।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> getModifiedArray(int n, vector<vector<int>>& a) {
        vector<int> ret(n);
        for (int i = 0; i < a.size(); i++) {
            int l = a[i][0];
            int r = a[i][1] + 1;
            ret[l] += a[i][2];
            if (r < n) {
                ret[r] -= a[i][2];
            }
        }
        for (int i = 1; i < n; i++) {
            ret[i] += ret[i - 1];
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{1,3,2},{2,4,3},{0,2,-2}};
    print_vector(ob.getModifiedArray(5, v));
    return 0;
}

ইনপুট

5, {{1,3,2},{2,4,3},{0,2,-2}}

আউটপুট

[-2, 0, 3, 5, 3, ]