क्वेरी नंतर सम क्रमांकांची बेरीज


अडचण पातळी सोपे
वारंवार विचारले खरंच
अरे

समस्या विधान

या समस्येमध्ये, आम्हाला एक दिले जाते अॅरे पूर्णांक आणि अ‍ॅरेचा अ‍ॅरे क्वेरी. साठी आयथ क्वेरी, आपल्याकडे दोन पॅरामीटर्स आहेत. निर्देशांक आणि व्हॉल. प्रत्येक क्वेरीनंतर आम्ही जोडतो मूल्य अ‍ॅरे [अनुक्रमणिका] करण्यासाठी. आपल्याला सर्वांची बेरीज शोधण्याची गरज आहे अगदी प्रत्येक क्वेरी नंतर अ‍ॅरे मध्ये पूर्णांक आणि पूर्णांक एक वेक्टर म्हणून परत करा.

उदाहरण

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 तपासून). जर होय, तर आम्ही ते चालू असलेल्या रकमेपासून वजा करतो आणि A [अनुक्रमणिका] A [अनुक्रमणिका] + व्हॉल म्हणून अद्यतनित करतो. त्यानंतर, आम्हाला पुन्हा एकदा [निर्देशांक] समान आहे की नाही हे तपासण्याची आवश्यकता आहे. जर होय, तर आम्ही त्यात भर घालू सम_सम. हे या क्वेरीचे उत्तर असेल कारण इतर सर्व सम घटक अप्रभावित राहतात. म्हणून आम्ही प्रत्येक क्वेरीचे उत्तर ओ (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

क्वेरीनंतर सम संख्येच्या योगाचे कॉम्प्लेक्सिटी विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन + क्यू), जेथे, दिलेल्या अ‍ॅरेचा एन = आकार. प्रश्न = क्वेरींची संख्या. आम्ही शोधण्यासाठी ओ (एन) वेळ घालवितो सम रक्कम आणि प्रत्येक क्वेरीचे उत्तर देण्यासाठी ओ (प्रश्न) वेळ.

स्पेस कॉम्प्लेक्सिटी 

ओ (1)आपण सतत मेमरी स्पेस वापरत आहोत.