LeetCode-Go 题解985. Sum of Even Numbers After Queries查询后偶数的和动态维护前缀思路【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文讲解 LeetCode 第 985 题「Sum of Even Numbers After Queries」在 LeetCode-Go 仓库中的完整解法。该题属于数组 动态维护经典题型每次查询会永久修改数组中的某个元素并要求立即返回当前数组中所有偶数值之和。读完本文你将掌握先统计、后增量维护的 O(n m) 线性解法理解偶数状态翻转的四种情形并能对照仓库源码与单元测试自行验证。题目描述给定一个整数数组A和一个查询数组queries。对于第i次查询val queries[i][0]index queries[i][1]需要把val加到A[index]上。随后第i次查询的答案是更新完成后数组A中所有偶数值之和。两个关键前提给定的index queries[i][1]是0-based下标每次查询都会永久修改数组A后续查询基于修改后的数组继续执行。最终返回答案数组answer其中answer[i]是第i次查询后的偶数和。示例Input: A [1,2,3,4], queries [[1,0],[-3,1],[-4,0],[2,3]] Output: [8,6,2,4] Explanation: At the beginning, the array is [1,2,3,4]. After adding 1 to A[0], the array is [2,2,3,4], and the sum of even values is 2 2 4 8. After adding -3 to A[1], the array is [2,-1,3,4], and the sum of even values is 2 4 6. After adding -4 to A[0], the array is [-2,-1,3,4], and the sum of even values is -2 4 2. After adding 2 to A[3], the array is [-2,-1,3,6], and the sum of even values is -2 6 4.数据约束1 A.length 10000-10000 A[i] 100001 queries.length 10000-10000 queries[i][0] 100000 queries[i][1] A.length注意约束中没有排除负数A[i]与val均可以为负。Go 中%运算对负数同样能得到 0当且仅当该数为偶数时因此判断奇偶只需v%2 0无需额外处理符号这是后续实现可以保持简洁的原因。解题思路先统计再动态维护朴素做法的代价最直观的做法是每次查询后重新遍历整个数组累加所有偶数时间复杂度为 O(m·n)m 为查询次数n 为数组长度。在本题约束下n、m 均可达 10⁴最坏需要 10⁸ 量级运算虽勉强可行但显然不是最优解也违背了每次查询只改动一个元素这一关键信息。核心洞察注意到每次查询只改变数组中的一个元素A[index]全局偶数和的变化完全取决于该元素的奇偶状态变化。因此不必每次全量扫描而可以预统计先遍历一次数组计算初始状态下所有偶数值之和cur增量维护对每条查询仅基于被修改元素A[index]的修改前状态与修改后状态来局部更新cur并记录答案。偶数和的四类增量情形设修改前该位置值为old A[index]修改后new old val分类讨论修改前 old修改后 new对偶数和 cur 的影响偶数偶数cur先减去old再加上new净变化为val偶数奇数cur减去old无需再加净变化为-old奇数偶数cur不变再加上new净变化为new奇数奇数cur完全不变实现上不必显式写四个分支先判断old是否为偶数若是则cur - old修改元素后再判断new是否为偶数若是则cur new。两次条件判断天然覆盖了上表全部四种情形且与修改顺序无关地保持了正确性。源码实现仓库中的完整实现位于 解法源码代码如下package leetcode func sumEvenAfterQueries(A []int, queries [][]int) []int { cur, res : 0, []int{} for _, v : range A { if v%2 0 { cur v } } for _, q : range queries { if A[q[1]]%2 0 { cur - A[q[1]] } A[q[1]] q[0] if A[q[1]]%2 0 { cur A[q[1]] } res append(res, cur) } return res }逐段拆解预统计阶段第一个for循环遍历数组A把所有偶数值累加到cur得到初始偶数和查询处理阶段第二个for循环if A[q[1]]%2 0 { cur - A[q[1]] }—— 若被修改元素修改前是偶数先从cur中移除它A[q[1]] q[0]—— 执行永久修改if A[q[1]]%2 0 { cur A[q[1]] }—— 若修改后是偶数再把新值加回curres append(res, cur)—— 记录本次查询后的偶数和。该实现未申请额外数组结果数组res是题目要求的返回值长度与查询数相同空间占用极小。复杂度分析时间复杂度O(n m)。预处理遍历数组一次 O(n)随后 m 条查询每条 O(1) 的常数操作总体线性空间复杂度O(m)仅用于存放返回的答案数组不含输入数组的拷贝若不计输出则辅助空间为 O(1)。对比朴素解法 O(m·n) 的时间复杂度动态维护思路在 m、n 同阶时拥有平方级的性能优势这也是本题考察的核心。边界情况与正确性论证结合约束条件可以从以下几个边界情形验证实现的鲁棒性val 为负数如示例中的[-3,1]与[-4,0]cur的增减完全由修改前后奇偶状态决定负值天然被纳入运算结果正确修改前后均为偶数cur先减旧值再加新值净效果等价于加上val因为偶 偶 仍为偶直接加val同样正确但统一走先减后加路径逻辑更自洽修改前后均为奇数两个条件判断均不满足cur保持不变与表格分析一致偶数值为 00是偶数0 % 2 0预统计与增量维护均会将其计入符合题目even values的定义单元素数组n 1 时预统计只累加一个元素每次查询只修改唯一位置逻辑同样成立。单元测试验证仓库为本题配套了单元测试 985. Sum of Even Numbers After Queries_test.go采用该仓库统一的问题测试模板question985/para985/ans985结构体分别承载题目序号、输入参数与期望输出qs : []question985{ { para985{[]int{1, 2, 3, 4}, [][]int{{1, 0}, {-3, 1}, {-4, 0}, {2, 3}}}, ans985{[]int{8, 6, 2, 4}}, }, }测试用例正是题目示例输入A [1,2,3,4]四组查询依次得到[8,6,2,4]与逐步推导完全一致。测试函数中通过fmt.Printf输出每次查询的输入与结果便于人工核对运行轨迹。运行全部测试可通过仓库根目录的 gotest.sh 脚本go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...其中./leetcode/...会递归覆盖leetcode目录下全部题目的用例本题实现与测试也包含在内。小结LeetCode 985 题是数组单点修改 全局聚合查询场景的入门范例它展示了不重复计算、只对变化点做增量更新的通用优化思想。该思路可以平移到区间查询、前缀和维护等更复杂的题型上。在 LeetCode-Go 仓库中本题以极简的 Go 实现与 100% 覆盖率测试用例沉淀了这一模式值得反复研读。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Go 题解：985. Sum of Even Numbers After Queries（查询后偶数的和，动态维护前缀思路）
LeetCode-Go 题解985. Sum of Even Numbers After Queries查询后偶数的和动态维护前缀思路【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文讲解 LeetCode 第 985 题「Sum of Even Numbers After Queries」在 LeetCode-Go 仓库中的完整解法。该题属于数组 动态维护经典题型每次查询会永久修改数组中的某个元素并要求立即返回当前数组中所有偶数值之和。读完本文你将掌握先统计、后增量维护的 O(n m) 线性解法理解偶数状态翻转的四种情形并能对照仓库源码与单元测试自行验证。题目描述给定一个整数数组A和一个查询数组queries。对于第i次查询val queries[i][0]index queries[i][1]需要把val加到A[index]上。随后第i次查询的答案是更新完成后数组A中所有偶数值之和。两个关键前提给定的index queries[i][1]是0-based下标每次查询都会永久修改数组A后续查询基于修改后的数组继续执行。最终返回答案数组answer其中answer[i]是第i次查询后的偶数和。示例Input: A [1,2,3,4], queries [[1,0],[-3,1],[-4,0],[2,3]] Output: [8,6,2,4] Explanation: At the beginning, the array is [1,2,3,4]. After adding 1 to A[0], the array is [2,2,3,4], and the sum of even values is 2 2 4 8. After adding -3 to A[1], the array is [2,-1,3,4], and the sum of even values is 2 4 6. After adding -4 to A[0], the array is [-2,-1,3,4], and the sum of even values is -2 4 2. After adding 2 to A[3], the array is [-2,-1,3,6], and the sum of even values is -2 6 4.数据约束1 A.length 10000-10000 A[i] 100001 queries.length 10000-10000 queries[i][0] 100000 queries[i][1] A.length注意约束中没有排除负数A[i]与val均可以为负。Go 中%运算对负数同样能得到 0当且仅当该数为偶数时因此判断奇偶只需v%2 0无需额外处理符号这是后续实现可以保持简洁的原因。解题思路先统计再动态维护朴素做法的代价最直观的做法是每次查询后重新遍历整个数组累加所有偶数时间复杂度为 O(m·n)m 为查询次数n 为数组长度。在本题约束下n、m 均可达 10⁴最坏需要 10⁸ 量级运算虽勉强可行但显然不是最优解也违背了每次查询只改动一个元素这一关键信息。核心洞察注意到每次查询只改变数组中的一个元素A[index]全局偶数和的变化完全取决于该元素的奇偶状态变化。因此不必每次全量扫描而可以预统计先遍历一次数组计算初始状态下所有偶数值之和cur增量维护对每条查询仅基于被修改元素A[index]的修改前状态与修改后状态来局部更新cur并记录答案。偶数和的四类增量情形设修改前该位置值为old A[index]修改后new old val分类讨论修改前 old修改后 new对偶数和 cur 的影响偶数偶数cur先减去old再加上new净变化为val偶数奇数cur减去old无需再加净变化为-old奇数偶数cur不变再加上new净变化为new奇数奇数cur完全不变实现上不必显式写四个分支先判断old是否为偶数若是则cur - old修改元素后再判断new是否为偶数若是则cur new。两次条件判断天然覆盖了上表全部四种情形且与修改顺序无关地保持了正确性。源码实现仓库中的完整实现位于 解法源码代码如下package leetcode func sumEvenAfterQueries(A []int, queries [][]int) []int { cur, res : 0, []int{} for _, v : range A { if v%2 0 { cur v } } for _, q : range queries { if A[q[1]]%2 0 { cur - A[q[1]] } A[q[1]] q[0] if A[q[1]]%2 0 { cur A[q[1]] } res append(res, cur) } return res }逐段拆解预统计阶段第一个for循环遍历数组A把所有偶数值累加到cur得到初始偶数和查询处理阶段第二个for循环if A[q[1]]%2 0 { cur - A[q[1]] }—— 若被修改元素修改前是偶数先从cur中移除它A[q[1]] q[0]—— 执行永久修改if A[q[1]]%2 0 { cur A[q[1]] }—— 若修改后是偶数再把新值加回curres append(res, cur)—— 记录本次查询后的偶数和。该实现未申请额外数组结果数组res是题目要求的返回值长度与查询数相同空间占用极小。复杂度分析时间复杂度O(n m)。预处理遍历数组一次 O(n)随后 m 条查询每条 O(1) 的常数操作总体线性空间复杂度O(m)仅用于存放返回的答案数组不含输入数组的拷贝若不计输出则辅助空间为 O(1)。对比朴素解法 O(m·n) 的时间复杂度动态维护思路在 m、n 同阶时拥有平方级的性能优势这也是本题考察的核心。边界情况与正确性论证结合约束条件可以从以下几个边界情形验证实现的鲁棒性val 为负数如示例中的[-3,1]与[-4,0]cur的增减完全由修改前后奇偶状态决定负值天然被纳入运算结果正确修改前后均为偶数cur先减旧值再加新值净效果等价于加上val因为偶 偶 仍为偶直接加val同样正确但统一走先减后加路径逻辑更自洽修改前后均为奇数两个条件判断均不满足cur保持不变与表格分析一致偶数值为 00是偶数0 % 2 0预统计与增量维护均会将其计入符合题目even values的定义单元素数组n 1 时预统计只累加一个元素每次查询只修改唯一位置逻辑同样成立。单元测试验证仓库为本题配套了单元测试 985. Sum of Even Numbers After Queries_test.go采用该仓库统一的问题测试模板question985/para985/ans985结构体分别承载题目序号、输入参数与期望输出qs : []question985{ { para985{[]int{1, 2, 3, 4}, [][]int{{1, 0}, {-3, 1}, {-4, 0}, {2, 3}}}, ans985{[]int{8, 6, 2, 4}}, }, }测试用例正是题目示例输入A [1,2,3,4]四组查询依次得到[8,6,2,4]与逐步推导完全一致。测试函数中通过fmt.Printf输出每次查询的输入与结果便于人工核对运行轨迹。运行全部测试可通过仓库根目录的 gotest.sh 脚本go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...其中./leetcode/...会递归覆盖leetcode目录下全部题目的用例本题实现与测试也包含在内。小结LeetCode 985 题是数组单点修改 全局聚合查询场景的入门范例它展示了不重复计算、只对变化点做增量更新的通用优化思想。该思路可以平移到区间查询、前缀和维护等更复杂的题型上。在 LeetCode-Go 仓库中本题以极简的 Go 实现与 100% 覆盖率测试用例沉淀了这一模式值得反复研读。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
 本书序言)
