[数据结构与算法]leetcode 985. Sum of Even Numbers After Queries（query之后的偶数和）

You are given an integer array nums and an array queries where queries[i] = [vali, indexi].

For each query i, first, apply nums[indexi] = nums[indexi] + vali, then print the sum of the even values of nums.

Return an integer array answer where answer[i] is the answer to the ith query.

Example 1:

Input: nums = [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 nums[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to nums[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to nums[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to nums[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.

有一个nums数组，每次query:[val, index]会产生nums[index] += val的效果。
最后要返回每次query之后nums中所有偶数的和。

思路：

每次只操作nums[index]一个数字，所以不需要每次都计算所有偶数的和，
刚开始的时候计算一次，后面每次就操作这一个数字。

这时候要分几种情况：
奇数是不会加到和里面去的，如果之前是奇数，现在是偶数，就要把现在的偶数加到和里面。
如果之前是偶数，现在是奇数，就要从现有的和里面减去之前的偶数，因为现在这个nums[index]不参与计算了。
之前是偶数，现在还是偶数，就加上差分的val部分即可。
之前奇数，现在还是奇数，都不参与计算，不需要处理。

所以这个思路整理成代码就是这样的。

public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
    int evenSum = 0;
    int[] res = new int[queries.length];
    int i = 0;
    
    for(int num : nums) {
        if(num % 2 == 0) evenSum += num;
    }
    
    for(int[] query : queries) {
        int val = query[0];
        int index = query[1];
        
        //previous odd, now even
        if(nums[index] % 2 != 0 && (nums[index]+val) % 2 == 0) evenSum += (nums[index] + val);
        //previous even, now even
        else if(nums[index] % 2 == 0 && (nums[index]+val) % 2 == 0) evenSum += val;
        //previous even, now odd
        else if(nums[index] % 2 == 0 && (nums[index]+val) % 2 != 0) evenSum -= nums[index];
        //previous odd, now odd
        //do nothing
        nums[index] += val;
        res[i++] = evenSum;
    }
    return res;
}

通过是能通过的，不过时间排名很靠后，
多次重复的计算nums[index] % 2 和 (nums[index]+val) % 2，
再整理一下，

需要处理的情况无非就是之前是（奇数，偶数），现在是（奇数，偶数）
之前是奇数时没参与计算，
之前是偶数时，把之前的偶数从和里减掉，就达到了“清零”操作。
然后看现在，
奇数不参与计算，
只需要看偶数的情况，偶数时把偶数加到和里面就好了。

同时，有个技巧，判断奇偶时，只需要判断最低的bit位是不是1.
不要忘了更新nums[index]。

public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
    int evenSum = 0;
    int[] res = new int[queries.length];
    int i = 0;
    
    for(int num : nums) {
        if(num % 2 == 0) evenSum += num;
    }
    
    for(int[] query : queries) {
        int val = query[0];
        int index = query[1];
        
        //previous even
        if((nums[index] & 1) == 0) evenSum -= nums[index];
        
        nums[index] += val;
        
        //now even
        if((nums[index] & 1) == 0) evenSum += nums[index];
        res[i++] = evenSum;
    }
    return res;
}