C++-এ রেঞ্জ সম কোয়েরি ও স্কোয়ার রুট আপডেট

অ্যারে ১-বেসড ইনডেক্সড ধরা হয়েছে।

উদাহরণ

ইনপুট: nums = {0,9,4,1,5,2,3}, Query = {{1,1,3},{2,1,2},{1,2,5},{1,4,5}}

আউটপুট: 14, 10, 7

স্টেপ-বাই-স্টেপ:

1. Query ১: রেঞ্জ ১-৩ সম = ৯+৪+১=১৪
2. Query ২: আপডেট ১-২ → নতুন অ্যারে: {3,2,1,5,2,3}
3. Query ৩: রেঞ্জ ২-৫ সম = ২+১+৫+২=১০
4. Query ৪: রেঞ্জ ৪-৫ সম = ৫+২=৭

অ্যালগরিদম

সিম্পল পদ্ধতি (O(q×n))

প্রতিটি কোয়েরির জন্য লুপ চালান। বড় ইনপুটে ধীর।

ইফিশিয়েন্ট পদ্ধতি: বাইনারি ইন্ডেক্সড ট্রি (Fenwick Tree) + সেট

1. Fenwick Tree বানান রেঞ্জ সম কোয়েরির জন্য।
2. একটি set রাখুন যেই ইনডেক্সগুলোwhose value > 1 (কারণ ১-এর স্কোয়ার রুট ১, আর আপডেট লাগে না)।
3. আপডেট কোয়েরিতে: lower_bound(L) দিয়ে প্রথম >১ ভ্যালু খুঁজুন, সেটি আপডেট করুন, যদি ১ হয়ে যায় তবে সেট থেকে মুছুন।
4. সম কোয়েরিতে: query(R) - query(L-1)।

C++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;
const int MAX = 200;
int BIT[MAX + 1];

void updateBIT(int idx, int delta, int n) {
    while (idx <= n) {
        BIT[idx] += delta;
        idx += idx & -idx;
    }
}

int queryBIT(int idx) {
    int sum = 0;
    while (idx > 0) {
        sum += BIT[idx];
        idx -= idx & -idx;
    }
    return sum;
}

int main() {
    int nums[] = {0, 9, 4, 1, 5, 2, 3};
    int n = sizeof(nums)/sizeof(nums[0]) - 1;
    int q[4][3] = {{1,1,3},{2,1,2},{1,2,5},{1,4,5}};
    set<int> s;
    for (int i = 1; i <= n; i++) {
        if (nums[i] > 1) s.insert(i);
        updateBIT(i, nums[i], n);
    }
    for (int i = 0; i < 4; i++) {
        if (q[i][0] == 2) { // Update
            while (true) {
                auto it = s.lower_bound(q[i][1]);
                if (it == s.end() || *it > q[i][2]) break;
                int idx = *it;
                int newVal = (int)sqrt(nums[idx]);
                updateBIT(idx, newVal - nums[idx], n);
                nums[idx] = newVal;
                if (nums[idx] == 1) s.erase(it);
                else q[i][1] = idx + 1;
            }
        } else { // Query
            cout << "query" << i+1 << ": " << queryBIT(q[i][2]) - queryBIT(q[i][1]-1) << endl;
        }
    }
    return 0;
}

আউটপুট

query1: 14
query3: 10
query4: 7

মূল পয়েন্ট

• Fenwick Tree দিয়ে O(log n)-এ রেঞ্জ সম।
• সেট দিয়ে শুধু >১ ভ্যালুवाले ইনডেক্স ট্র্যাক → আপডেট ফাস্ট।
• একবার ১ হলে সেট থেকে রিমুভ → ফিউচার আপডেটে স্কিপ।
• টোটাল কমপ্লেক্সিটি: O((n+q) log n) (প্রায়)।