রেঞ্জ সম কুয়েরি বিনা আপডেট (C++)

একটি অ্যারে দেওয়া আছে। ইন্ডেক্স i থেকে j পর্যন্ত উপাদানগুলোর যোগফল বের করতে হবে (বেশি কুয়েরি থাকলে)। প্রিফিক্স সম (prefix sum) অ্যারে বানিয়ে O(1)-এ কুয়েরি আন্সার করুন।

উদাহরণ

#include <iostream>
using namespace std;

int rangeSum(int i, int j, int prefix[]) {
    if (i == 0) return prefix[j];
    return prefix[j] - prefix[i-1];
}

int main() {
    int arr[] = {5,6,3,4,1};
    int n = 5, prefix[5];
    prefix[0] = arr[0];
    for (int i = 1; i < n; i++) prefix[i] = prefix[i-1] + arr[i];
    cout << rangeSum(1, 3, prefix); // 6+3+4=13
    return 0;
}

আউটপুট

13