মান লোয়া একটি ইন্টিজার অ্যারে। আমাদের i থেকে j ইনডেক্স পর্যন্ত উপাদানগুলোর যোগফল বের করতে হবে। দুটি বিষয় খোঁজে রাখতে হবে: অ্যারে ইমিউটেবল (immutable), অর্থাৎ উপাদানগুলো পরিবর্তন করা যাবে না, এবং একাধিক এমন কোয়েরি থাকবে। তাই অনেক কোয়েরির জন্য এক্সিকিউশন টাইম খোঁজে রাখতে হবে। ধরুন অ্যারে A = [5, 8, 3, 6, 1, 2, 5], তবে কোয়েরি (A, 0, 3) হলে ফলাফল হবে 5 + 8 + 3 + 6 = 22।
এটি সমাধানের জন্য আমরা নিচের ধাপগুলো অনুসরণ করব −
- একটি B অ্যারে নিন। B[i] সংরক্ষণ করবে 0 থেকে i ইনডেক্স পর্যন্ত উপাদানগুলোর যোগফল
- কোয়েরির জন্য B[j] – B[i – 1] করুন
নিচের ইমপ্লিমেন্টেশন দেখে ভালোভাবে বুঝতে পারবেন −
উদাহরণ
#include <bits/stdc++.h> using namespace std; class NumArray { public: vector <int> pre; NumArray(vector<int>& nums) { pre.clear(); int n = nums.size(); pre.resize(n); for(int i = 0; i < n; i++){ if(i == 0)pre[0] = nums[0]; else pre[i] = pre[i - 1] + nums[i]; } } int sumRange(int i, int j) { if(i == 0)return pre[j]; return pre[j] - pre[i - 1]; } }; main(){ vector<int> v = {5,8,3,6,1,2,5}; NumArray na(v); cout<<na.sumRange(0,2)<<endl; cout<<na.sumRange(2,5)<<endl; cout<<na.sumRange(0,5)<<endl; }ইনপুট
Initialize it with [5,8,3,6,1,2,5] Call sumRange(0,2) sumRange(2,5) sumRange(0,5)
আউটপুট
16 12 25
