题目描述
思路解析
一句话答案：LeetCode 985 查询后的偶数和：每次给某个位置加一个值，再问此刻偶数和，靠增量维护——旧偶先减、新偶再加、不重扫，时间 O(n+q)、空间 O(1)。
每次查询改一个数，要你回答什么
给一个整数数组 nums 和一串查询 queries。第 i 次查询给你 val 和 index，先把 val 加到 nums[index] 上，改动永久保留，下一次在改过的数组上接着来；加完后这次答案就是此刻 nums 里所有偶数的和。题面例子 nums=[1,2,3,4]，queries=[[1,0],[-3,1],[-4,0],[2,3]]，返回 [8,6,2,4]。
每次都把数组重扫一遍，这笔账付得起吗
直白的做法是：每次改完那格就从头扫一遍数组，把偶数挑出来相加。一次扫描 O(n)，q 次查询就是 O(n·q)。本题 n 和 q 都能到一万，相乘一亿次加法，稳稳超时。浪费在于每次都重算那些没被碰过的数——值和奇偶都没变，白扫。
凭什么只动一个位置，就能更新整盘的和
一次查询只改一个格子，别的 n-1 个数纹丝不动，对偶数和的贡献也没变。所以和不必重算，只要盯住被改的那格：它原来是不是偶数、改完是不是偶数，把差额补进一个专记当前偶数和的变量 evenSum。这就是增量维护——先花一遍 O(n) 求出初始偶数和当起点，之后每次查询只在它上面做常数次加减。
旧值新值各判一次奇偶，四种走向怎么转
每次查询拆成三拍：改值前先看旧值、真正改值、改完再看新值。旧值若是偶数，它此刻正躺在 evenSum 里、马上要被换掉，得先减出去；旧值若是奇数，本没进 evenSum，不用动。改完的新值是偶数就加进 evenSum，是奇数就不加。
旧值奇偶两种、新值奇偶两种，交叉出四种走向：旧奇变新奇不动；旧奇变新偶只加新值；旧偶变新奇只减旧值；旧偶变新偶先减旧再加新。这两次判断彼此独立，别拿旧值奇偶替新值下结论。
四次查询在 [1,2,3,4] 上依次算，答案怎么来
起点：nums=[1,2,3,4] 里 2 和 4 是偶数，evenSum 初始 2+4=6，发生在所有查询之前。
第 1 次 [1,0]：旧值 nums[0]=1 奇、不减，加 1 变 2 偶、evenSum 6+2=8，答案 8。第 2 次 [-3,1]：旧值 nums[1]=2 偶、先减 8-2=6，加 -3 变 -1 奇、不加，答案 6。第 3 次 [-4,0]：nums[0]=2 偶、先减 6-2=4，加 -4 变 -2 偶、4-2=2，答案 2。第 4 次 [2,3]：nums[3]=4 偶、先减 2-4=-2，加 2 变 6 偶、-2+6=4，答案 4。四个答案连起来就是 [8,6,2,4]。
改值前漏减旧偶，和就悄悄偏大了
这套流程最容易漏改值前那次减法：旧值分明是偶数，却直接加新值、忘了先从 evenSum 撤出去，旧的那份赖着不走，结果一路偏大。另一处是拿旧值奇偶替新值下结论——旧偶才减、新偶才加，漏判哪个都算错。两个边界记牢：0 算偶数，变成 0 要加、从 0 变奇数要减；连着两次改同一格也不特殊，第二次读到的就是上次改完的值。复杂度上初始求和 O(n)，之后每次查询常数时间、共 q 次，合起来 O(n+q)，比重扫的 O(n·q) 快一个数量级；额外只用 evenSum 一个变量，空间 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套「旧偶先减、改值、新偶再加」，下面每次查询都在套它。一个数从偶变奇要减掉，从奇变偶要加上，evenSum 始终是当前真实的偶数和。
开局先把起始数组里的偶数找出来。这里 2 和 4 是偶数（绿色），1 和 3 是奇数。先把它们的和当作 evenSum 的起点。
两个偶数 2 和 4 加起来，evenSum 起始等于 6。注意这一步是查询开始前的准备，还没产生任何答案。接下来每次查询都在这个 6 上增量更新。
第 1 次查询来了，要把 1 加到下标 0（紫色这格，现在是 1）。别急着加，按套路先看这个旧值 1 是奇是偶。
旧值 1 是奇数，它根本没被算进偶数和，所以不用减，evenSum 还是 6。奇数被改不影响已有的偶数和。
现在真正执行加法，下标 0 从 1 变成 2。偶数和先按兵不动，等下看这个新值 2 是不是偶数再决定加不加。
新值 2 是偶数，把它加进偶数和：6 + 2 等于 8。这就是第 1 次查询的答案，记进右边的答案表。
第 2 次查询来了，要把 -3 加到下标 1（紫色这格，现在是 2）。别急着加，按套路先看这个旧值 2 是奇是偶。
旧值 2 是偶数，它现在还待在偶数和里。马上要改它，所以先把它从 evenSum 减出去：8 - 2 等于 6。红色表示这个旧偶数即将离场。
现在真正执行加法，下标 1 从 2 变成 -1。偶数和先按兵不动，等下看这个新值 -1 是不是偶数再决定加不加。
新值 -1 是奇数，进不了偶数和，evenSum 仍是 6。这就是第 2 次查询的答案，照样记进答案表。
第 3 次查询来了，要把 -4 加到下标 0（紫色这格，现在是 2）。别急着加，按套路先看这个旧值 2 是奇是偶。
旧值 2 是偶数，它现在还待在偶数和里。马上要改它，所以先把它从 evenSum 减出去：6 - 2 等于 4。红色表示这个旧偶数即将离场。
现在真正执行加法，下标 0 从 2 变成 -2。偶数和先按兵不动，等下看这个新值 -2 是不是偶数再决定加不加。
新值 -2 是偶数，把它加进偶数和：4 - 2 等于 2。这就是第 3 次查询的答案，记进右边的答案表。
第 4 次查询来了，要把 2 加到下标 3（紫色这格，现在是 4）。别急着加，按套路先看这个旧值 4 是奇是偶。
旧值 4 是偶数，它现在还待在偶数和里。马上要改它，所以先把它从 evenSum 减出去：2 - 4 等于 -2。红色表示这个旧偶数即将离场。
现在真正执行加法，下标 3 从 4 变成 6。偶数和先按兵不动，等下看这个新值 6 是不是偶数再决定加不加。
新值 6 是偶数，把它加进偶数和：-2 + 6 等于 4。这就是第 4 次查询的答案，记进右边的答案表。
四次查询都处理完了。最终数组是 [-2, -1, 3, 6]，绿色的 -2 和 6 是当前仅剩的偶数，它们的和正是最后一次的答案 4。
回头看，我们从头到尾没把整个数组重新加过一遍。每次查询只动一个位置，旧偶先减、新偶再加，evenSum 一路都是对的。这就是增量维护的省力之处。
边界先想清：奇数让和为 0、连续两次改同一格、以及 0 本身算偶数这几种情形。
两个高频追问，重点讲清「为何增量」与「会不会溢出」。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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复杂度
- 时间：O(n + q)，初始求和扫一遍 O(n)，之后每次查询 O(1)，共 q 次
- 空间：O(1)，只多用一个 evenSum 变量（不计必须返回的答案数组）
易错点
面试追问把动画讲成自己的话
追问为什么不能每次查询都重新遍历数组求偶数和？
追问如果数值范围很大，结果会溢出吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
按列翻转得到最大值等行数
LeetCode 1072 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题