クエリ後の偶数の合計


難易度 簡単に
よく聞かれる 確かに
配列

問題文

この問題では、 配列 整数と配列の配列 クエリ   i番目 クエリでは、XNUMXつのパラメータがあります。 index val。 各クエリの後に、追加します ヴァル array [index]に。 すべての合計を見つける必要があります さらに 各クエリの後に配列内の整数を返し、整数のベクトルとして返します。

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

アプローチ

クエリ後の偶数の合計の実装

基本的なアプローチのXNUMXつは次のとおりです。

クエリごとに、対応する要素を更新してから、配列全体をトラバースして、すべての偶数の合計を見つけます。 ただし、このアプローチでは、クエリごとにO(N)時間がかかり、全体の時間がO(N * Q)になります。

私たちは維持することによってより良くすることができます 事前合計 これは、配列内のすべての偶数の合計です。 クエリごとに、そのインデックスの要素がに貢献していたかどうかを確認できます 合計でも 以前に計算されました(A [index]%2 == 0かどうかをチェックすることによって)。 はいの場合、現在の合計からそれを減算し、A [index]をA [index] + valとして更新します。 その後、A [index]が偶数かどうかを再度確認する必要があります。 はいの場合、に追加します even_sum。 他のすべての偶数要素は影響を受けないため、これがそのクエリの答えになります。 したがって、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;
}

Javaプログラム

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(1)、一定のメモリスペースを使用するため。