题目描述

我们有一个整数数组 A 和一组询问。

对于第 i 个询问 val = queries[i][0], index = queries[i][1]，我们将 val 加到 A[index] 中。 然后，第 i 次询问的答案就是 A 中所有偶数元素的总和。

（这里，给定的 index = queries[i][1] 是以 0 为基础的下标，每一个询问都会永久得修改 A 数组）

返回所有询问的答案，你的答案数组中 answer[i] 是第 i 次询问的答案。

样例

输入：A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
输出：[8,6,2,4]
解释：
初始时，数组是 [1,2,3,4]
A[0] 加了 1 后，数组是 [2,2,3,4]，偶数元素的总和是 2 + 2 + 4 = 8。
A[1] 加了 -3 后，数组是 [2,-1,3,4]，偶数元素的总和是 2 + 4 = 6。
A[0] 加了 -4 后，数组是 [-2,-1,3,4]，偶数元素的总和是 -2 + 4 = 2。
A[3] 加了 2 后，数组是 [-2,-1,3,6]，偶数元素的总和是 -2 + 6 = 4。

注意

• 1 <= A.length <= 10000
• -10000 <= A[i] <= 10000
• 1 <= queries.length <= 10000
• -10000 <= queries[i][0] <= 10000
• 0 <= queries[i][1] < A.length

算法

(预处理+分类讨论) $O(n + q)$

1. 首先预处理出当前数组中所有偶数元素之和 sum。
2. 对于每个询问，分四种情况讨论：val 和 A[index] 都是偶数；val 为偶数 A[index] 为奇数；val 为奇数 A[index] 为偶数；val 和 A[index] 都是奇数。
3. 对于每种情况分别处理 sum 的值，然后修改 A[index]。

时间复杂度

• 预处理需要 $O(n)$ 的时间，每次询问需要 $O(1)$ 的时间，故总时间复杂度为 $O(n + q)$，其中 $q$ 为询问的个数。

空间复杂度

• 需要一个数组记录所有的答案，故空间复杂度为 $O(q)$。

C++ 代码

class Solution {
public:
    vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {
        int n = A.size(), sum = 0;
        for (int i = 0; i < n; i++)
            if (A[i] % 2 == 0)
                sum += A[i];
        vector<int> ans;
        for (int i = 0; i < queries.size(); i++) {
            int val = queries[i][0], index = queries[i][1];
            if (val % 2 == 0) {
                if (A[index] % 2 == 0) {
                    sum += val;
                }
            } else {
                if (A[index] % 2 == 0) {
                    sum -= A[index];
                } else {
                    sum += A[index] + val;
                }
            }
            A[index] += val;
            ans.push_back(sum); 
        }
        return ans;
    }
};