0985. 查询后的偶数和【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 偶数和维护

1. 📝 题目描述

• leetcode

给出一个整数数组 A 和一个查询数组 queries。

对于第 i 次查询，有 val = queries[i][0], index = queries[i][1]，我们会把 val 加到 A[index] 上。然后，第 i 次查询的答案是 A 中偶数值的和。

（此处给定的 index = queries[i][1] 是从 0 开始的索引，每次查询都会永久修改数组 A。）

返回所有查询的答案。你的答案应当以数组 answer 给出，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]。
将 1 加到 A[0] 上之后，数组为 [2,2,3,4]，偶数值之和为 2 + 2 + 4 = 8。
将 -3 加到 A[1] 上之后，数组为 [2,-1,3,4]，偶数值之和为 2 + 4 = 6。
将 -4 加到 A[0] 上之后，数组为 [-2,-1,3,4]，偶数值之和为 -2 + 4 = 2。
将 2 加到 A[3] 上之后，数组为 [-2,-1,3,6]，偶数值之和为 -2 + 6 = 4。

---

提示：

1. 1 <= A.length <= 10000
2. -10000 <= A[i] <= 10000
3. 1 <= queries.length <= 10000
4. -10000 <= queries[i][0] <= 10000
5. 0 <= queries[i][1] < A.length

2. 🎯 s.1 - 偶数和维护

js

/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {number[]}
 */
var sumEvenAfterQueries = function (nums, queries) {
  // 初始化偶数和
  let evenSum = 0
  for (const num of nums) {
    if (num % 2 === 0) {
      evenSum += num
    }
  }

  const result = []

  for (const [val, index] of queries) {
    const oldVal = nums[index]
    const newVal = oldVal + val

    // 如果原值是偶数，先从偶数和中减去
    if (oldVal % 2 === 0) {
      evenSum -= oldVal
    }

    // 更新数组值
    nums[index] = newVal

    // 如果新值是偶数，加到偶数和中
    if (newVal % 2 === 0) {
      evenSum += newVal
    }

    result.push(evenSum)
  }

  return result
}

• 时间复杂度：$O(n+q)$，其中 n 是数组长度，q 是查询次数，需要初始化偶数和并处理所有查询
• 空间复杂度：$O(1)$，只使用常数级别的额外空间

算法思路：

• 初始化偶数和：遍历数组计算所有偶数的和作为初始值
• 查询处理：对每个查询，根据修改前后的奇偶性变化来更新偶数和
• 奇偶性判断：如果原值是偶数，先从偶数和中减去；如果新值是偶数，加到偶数和中
• 状态更新：更新数组对应位置的值为新值
• 结果记录：每次查询后将当前偶数和加入结果数组