查询后的偶数和 图解题解

每次查询改一个数，要你回答什么

给一个整数数组 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)。

Python

from __future__ import annotations
from 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 = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<int> sumEvenAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        int s = 0;
        for (int x : nums) {
            if (x % 2 == 0) {
                s += x;
            }
        }
        vector<int> ans;
        for (auto& q : queries) {
            int v = q[0], i = q[1];
            if (nums[i] % 2 == 0) {
                s -= nums[i];
            }
            nums[i] += v;
            if (nums[i] % 2 == 0) {
                s += nums[i];
            }
            ans.push_back(s);
        }
        return ans;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
        int s = 0;
        for (int x : nums) {
            if (x % 2 == 0) {
                s += x;
            }
        }
        int m = queries.length;
        int[] ans = new int[m];
        int k = 0;
        for (int[] q : queries) {
            int v = q[0], i = q[1];
            if (nums[i] % 2 == 0) {
                s -= nums[i];
            }
            nums[i] += v;
            if (nums[i] % 2 == 0) {
                s += nums[i];
            }
            ans[k++] = s;
        }
        return ans;
    }
}