প্রশ্নের পরেও সংখ্যার যোগফল


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় প্রকৃতপক্ষে
বিন্যাস

সমস্যা বিবৃতি

এই সমস্যায়, আমাদের একটি দেওয়া হয় বিন্যাস পূর্ণসংখ্যা এবং অ্যারের অ্যারে of প্রশ্নের। জন্য সন্তান ক্যোয়ারী, আমাদের দুটি পরামিতি থাকবে, সূচক এবং Val। প্রতিটি প্রশ্নের পরে, আমরা যুক্ত Val অ্যারে [সূচি]। আমাদের সবার যোগফল খুঁজে পাওয়া দরকার এমন কি প্রতিটি ক্যোয়ারির পরে অ্যারেতে পূর্ণসংখ্যা এবং এটি পূর্ণসংখ্যার ভেক্টর হিসাবে ফিরিয়ে দেয়।

উদাহরণ

A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
8 6 2 4
A = [1,2,3,4], queries = [[2,0],[-2,2],[6,0],[4,2]]
6 6 6 6

অভিগমন

প্রশ্নের পরেও সংখ্যার যোগফল বাস্তবায়ন

একটি প্রাথমিক পদ্ধতির হ'ল:

প্রতিটি ক্যোয়ারির জন্য, সংশ্লিষ্ট উপাদানটি আপডেট করুন এবং তারপরে সমস্ত সমান সংখ্যার যোগফল খুঁজতে পুরো অ্যারেটি পেরিয়ে যান। তবে, এই পদ্ধতির ক্ষেত্রে ও (এন * কিউ) সামগ্রিক সময় নেওয়ার প্রতিটি প্রশ্নের জন্য ও (এন) সময় লাগবে।

আমরা একটি বজায় রেখে আরও ভাল করতে পারি প্রাক যোগফল যা অ্যারের সমস্ত সমান সংখ্যার যোগফল। প্রতিটি প্রশ্নের জন্য, আমরা এটির সূচকের উপাদানটি অবদান রাখছিল কিনা তা পরীক্ষা করতে পারি এমনকি যোগফল পূর্বে গণনা করা হয়েছে (A [সূচি]% 2 == 0 কিনা তা পরীক্ষা করে)। যদি হ্যাঁ, আমরা এটিকে চলমান যোগফল থেকে বিয়োগ করে এ [সূচক] + এ [সূচক] + ভাল হিসাবে আপডেট করব। এর পরে, আমাদের আবার [সূচি] সমান কিনা তা পরীক্ষা করে দেখতে হবে। যদি হ্যাঁ, আমরা এটি যুক্ত করি add even_sum। এটি অন্যান্য প্রশ্নের এমনকি উপাদানগুলি প্রভাবিত না থাকায় এটি এই প্রশ্নের উত্তর হবে। সুতরাং, আমরা ও (1) সময়ে প্রতিটি প্রশ্নের উত্তর দিই।

সি ++ প্রোগ্রাম

#include <bits/stdc++.h>

using namespace std;

vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {
    int evenSum = 0;

    for(int &x : A) {
        if(x % 2 == 0) {
            evenSum += x;
        }
    }

    int n = queries.size() , val , idx;
    vector <int> ans(n);
    for(int i = 0 ; i < n ; i++) {
        val = queries[i][0] , idx = queries[i][1];
        if(A[idx] % 2 == 0) evenSum -= A[idx];
        A[idx] += val;
        if(A[idx] % 2 == 0) evenSum += A[idx];
        ans[i] = evenSum;
    }

    return ans;
}

int main() {
    vector <int> A = {1 , 2 , 3 , 4};
    vector < vector <int> > queries = {{1 , 0} , {-3 , 1} , {-4 , 0} , {2 , 3}};
    vector <int> ans = sumEvenAfterQueries(A , queries);
    for(int &x : ans)
        cout << x << " ";
    cout << endl;
    return 0;
}

জাভা প্রোগ্রাম

class sum_even_after_queries {
    public static void main(String args[]) {
        int[] A = {1 , 2 , 3 , 4};
        int[][] queries = {{1 , 0} , {-3 , 1} , {-4 , 0} , {2 , 3}};
        int[] ans = sumEvenAfterQueries(A , queries);
        for(int x : ans)
            System.out.print(x + " ");
        System.out.println();
    }

    public static int[] sumEvenAfterQueries(int[] A, int[][] queries) {
        int evenSum = 0;

        for(int x : A) {
            if(x % 2 == 0) {
                evenSum += x;
            }
        }
        int n = queries.length , val , idx;
        int[] ans = new int[n];
        for(int i = 0 ; i < n ; i++) {
            val = queries[i][0];
            idx = queries[i][1];

            if(A[idx] % 2 == 0) evenSum -= A[idx];
            A[idx] += val;
            if(A[idx] % 2 == 0) evenSum += A[idx];
            ans[i] = evenSum;
        }

        return ans;
    }
}
8 6 2 4

প্রশ্নের পরেও যোগফলের জটিলতার বিশ্লেষণ

সময় জটিলতা

ও (এন + কিউ), যেখানে, প্রদত্ত অ্যারের N = আকার। প্রশ্ন = প্রশ্নের সংখ্যা। আমরা এটি পেতে ও (এন) সময় ব্যয় করি এমনকি যোগফল এবং ও (Q) সময় প্রতিটি প্রশ্নের উত্তর দিতে।

স্পেস জটিলতা ity 

ও (1)যেমন আমরা স্থির মেমরির স্থান ব্যবহার করি।