جمع اعداد زوج پس از پرس و جو


سطح دشواری ساده
اغلب در در واقع
صف

بیان مسأله

در این مشکل ، به ما داده می شود صف از عدد صحیح و آرایه ها س quالات برای i ام پرس و جو ، ما دو پارامتر خواهیم داشت ، شاخص و وال بعد از هر پرس و جو ، اضافه می کنیم وال به آرایه [فهرست]. ما باید مجموع همه را پیدا کنیم حتی اعداد صحیح در آرایه را پس از هر پرس و جو ، و آن را به عنوان بردار از اعداد صحیح برگردانید.

مثال

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 می توانیم بهتر عمل کنیم پیش جمع که مجموع تمام اعداد زوج در آرایه است. برای هر پرس و جو ، می توانیم بررسی کنیم که آیا عنصر موجود در شاخص آن به این موضوع کمک کرده است یا خیر حتی جمع زودتر محاسبه شد (با بررسی اینکه A [index]٪ 2 == 0). اگر بله ، آن را از جمع در حال اجرا کم می کنیم و A [index] را به صورت A [index] + val به روز می کنیم. پس از آن ، ما باید دوباره یکنواخت A [index] را بررسی کنیم. اگر بله ، آن را به اضافه می کنیم حتی_خلاصه. این پاسخ برای این سeryال خواهد بود زیرا سایر عناصر حتی یکسان نیستند. از این رو ، ما هر پرس و جو را در زمان O (1) پاسخ می دهیم.

برنامه 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 = تعداد سeriesالات. ما زمان O (N) را صرف پیدا کردن می کنیم حتی جمع و زمان پاسخ O (Q) به هر پرسش.

پیچیدگی فضا 

O (1)، همانطور که از فضای حافظه ثابت استفاده می کنیم.