प्रश्नहरूको पछाडि नम्बरहरूको योगफल


कठिनाई तह सजिलो
बारम्बार सोधिन्छ वास्तवमा
एरे

समस्या वक्तव्य

यस समस्यामा, हामीलाई एक दिइन्छ array पूर्णांक र एर्रेको एरे प्रश्नहरू। लागि ith क्वेरी, हामीसँग दुई प्यारामिटरहरू छन्, सूचकांक भोल प्रत्येक क्वेरी पछि, हामी थप्छौं 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

दृष्टिकोण

प्रश्नहरूको पछाडि संख्याको योगको कार्यान्वयन

एउटा आधारभूत दृष्टिकोण:

प्रत्येक क्वेरीको लागि, सम्बन्धित एलिमेन्ट अपडेट गर्नुहोस्, र पूरै एर्रेको पार गर्नुहोस् सबै संख्याहरूको योग फेला पार्न। तर यो दृष्टिकोणले O (N) समय लिने प्रत्येक प्रश्नको लागि O (N * Q) समग्र समय हुन्छ।

हामी a लाई राम्रोसँग राख्न सक्दछौं पूर्व योग जुन एर्रेमा सबै पनी संख्याको योग हो। प्रत्येक क्वेरीका लागि हामी जाँच गर्न सक्दछौं कि सूचकांकमा तत्त्वले योगदान गरिरहेको छ कि छैन योगफल पहिले गणना गरिएको (यदि [[अनुक्रमणिका]% 2 == ० जाँच गर्दै भने)। यदि हो भने, हामी यसलाई चालू योगबाट घटाउँछौं र A [अनुक्रमणिका] A [अनुक्रमणिका] + भेलको रूपमा अपडेट गर्दछौं। त्यस पछि, हामीले फेरि जाँच गर्नु पर्छ कि A [अनुक्रमणिका] समान छ कि छैन। यदि हो भने, हामी यसलाई जोड्दछौं even_sum। यो क्वेरीको लागि उत्तर हो किनकि सबै अन्य तत्वहरू अप्रभावित रहन्छन्। तसर्थ, हामी प्रत्येक क्वेरी ओ (१) समयमा जवाफ दिन्छौं।

C ++ कार्यक्रम

#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

प्रश्नहरूको पछाडि संख्याहरूको योगफलको जटिलता विश्लेषण

समय जटिलता

O (N + Q), कहाँ, दिइएको एर्रेको N = आकार। Q = प्रश्नहरूको संख्या। हामी O (N) समय खोज्नको लागि खर्च गर्दछौं योगफल र O (Q) समय प्रत्येक प्रश्नको उत्तर दिन।

ठाउँ जटिलता 

O (१), जब हामी स्थिर मेमोरी स्पेस प्रयोग गर्छौं।