What is the key pattern to solve Sum of Even Numbers After Queries efficiently?

The problem follows the Array plus Simulation pattern, where incremental updates to a running even sum avoid full recomputation.

Why is recalculating the sum from scratch after each query inefficient?

Recomputing the sum for each query results in O(N*Q) time complexity, which exceeds limits for large arrays and queries.

How do negative numbers affect the sum updates?

Negative numbers can change an element from even to odd or vice versa, so the running sum must be adjusted carefully after each update.

Can this approach be adapted to other conditions besides even numbers?

Yes, the incremental update strategy works for any condition that can be checked per element, like odd numbers or multiples of k.

What is the space complexity of the solution?

The space complexity is O(Q) due to storing the result array of sums after each query, with minimal additional overhead.

#985

Medium

auto_awesome数组·模拟

LeetCode 题解工作台

查询后的偶数和

给出一个整数数组 A 和一个查询数组 queries 。对于第 i 次查询，有 val = queries[i][0], index = queries[i][1] ，我们会把 val 加到 A[index] 上。然后，第 i 次查询的答案是 A 中偶数值的和。（此处给定的 index = qu…

数组模拟

题目描述

给出一个整数数组 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 <= A.length <= 10000
-10000 <= A[i] <= 10000
1 <= queries.length <= 10000
-10000 <= queries[i][0] <= 10000
0 <= queries[i][1] < A.length

lightbulb

解题思路

方法一：模拟

我们用一个整型变量 $\textit{s}$ 记录数组 $\textit{nums}$ 中所有偶数的和，初始时 $\textit{s}$ 为数组 $\textit{nums}$ 中所有偶数的和。

对于每次查询 $(v, i)$ ，我们首先判断 $\textit{nums}[i]$ 是否为偶数，若 $\textit{nums}[i]$ 为偶数，则将 $\textit{s}$ 减去 $\textit{nums}[i]$ ；然后将 $\textit{nums}[i]$ 加上 $v$ ；若 $\textit{nums}[i]$ 为偶数，则将 $\textit{s}$ 加上 $\textit{nums}[i]$ ，然后将 $\textit{s}$ 加入答案数组。

时间复杂度 $O(n + m)$ ，其中 $n$ 和 $m$ 分别为数组 $\textit{nums}$ 和 $\textit{queries}$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def sumEvenAfterQueries(
        self, nums: List[int], queries: List[List[int]]
    ) -> List[int]:
        s = sum(x for x in nums if x % 2 == 0)
        ans = []
        for v, i in queries:
            if nums[i] % 2 == 0:
                s -= nums[i]
            nums[i] += v
            if nums[i] % 2 == 0:
                s += nums[i]
            ans.append(s)
        return ans

speed

复杂度分析

指标	值
时间	O(N+Q)
空间	O(Q)

psychology

面试官常问的追问

外企场景

question_mark
Look for an approach that avoids recomputing the sum after each query.
question_mark
Expect recognition of the Array plus Simulation pattern and its incremental nature.
question_mark
Check for correct handling of negative numbers and zero when updating even sums.

warning

常见陷阱

外企场景

error
Recomputing the sum of even numbers from scratch after each query, causing TLE.
error
Failing to remove the old value from the sum before updating an element.
error
Not correctly identifying whether a value is even after the update, leading to wrong sums.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Sum of odd numbers after queries using the same incremental update technique.
arrow_right_alt
Counting numbers divisible by k after each query instead of even numbers.
arrow_right_alt
Tracking both even and odd sums simultaneously after each query for multi-condition updates.

help

常见问题

外企场景

继续练习

#999 可以被一步捕获的棋子数 #950 按递增顺序显示卡牌 #946 验证栈序列