쿼리 후 짝수 합계

문제 정책

이 문제에서 우리는 정렬 정수 및 배열 배열 검색어. 다음 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 [index] % 2 == 0인지 확인하여). 그렇다면 누적 합계에서 빼고 A [index]를 A [index] + val로 업데이트합니다. 그런 다음 A [index]가 짝수인지 다시 확인해야합니다. 그렇다면 다음 항목에 추가합니다. 짝수_합. 다른 모든 짝수 요소는 영향을받지 않기 때문에이 쿼리에 대한 답이 될 것입니다. 따라서 우리는 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 = 쿼리 수. 우리는 O (N) 시간을 투자하여 짝수 합계 각 질의에 응답하는 O (Q) 시간.

공간 복잡성 

O (1), 우리는 일정한 메모리 공간을 사용합니다.