Sum of Even Numbers After Queries: Incremental Even Sum Tracking

You are given an integer array nums and an array of queries. Each query [val, index] tells you to add val to nums[index]. After applying each query, you need to report the sum of all even-valued elements in nums.

This is LeetCode 985: Sum of Even Numbers After Queries, a medium problem that tests whether you can maintain a running aggregate efficiently. The naive approach recalculates the even sum after every query. The key insight is that each query only changes one element, so you can adjust the running sum in constant time.

Why this problem matters

At first glance, this looks like a simple simulation problem: apply each query, scan the array, sum the even values, repeat. That approach works, but it is slow. With up to 10,000 elements and 10,000 queries, scanning the entire array after each query gives you O(n * q) time. The real challenge is recognizing that you do not need to rescan.

This problem teaches a pattern that appears constantly in competitive programming and real-world systems: maintaining a running aggregate under point updates. Databases do this with materialized views. Caching systems do this when a single entry changes and you need to update a derived metric. The principle is always the same. If only one element changes, you should only pay for the cost of that one change.

Once you learn to think incrementally, you start seeing this optimization everywhere. Any time you are recomputing an aggregate from scratch inside a loop, ask yourself: can I adjust the previous result instead?

The brute force approach

def sumEvenAfterQueries(nums, queries):
    answer = []
    for val, index in queries:
        nums[index] += val
        total = sum(x for x in nums if x % 2 == 0)
        answer.append(total)
    return answer

This works correctly but runs in O(n * q) time. For each of the q queries, you iterate through all n elements to find and sum the even ones. When n and q are both large, this becomes too slow.

The key insight: incremental even sum adjustment

Instead of recalculating the entire even sum after each query, maintain a running total. Before applying a query, check whether the old value at nums[index] was even. If it was, subtract it from the running sum. Then apply the update. After the update, check whether the new value is even. If it is, add it to the running sum.

This works because the query only modifies one element. Every other element in the array stays the same, so their contribution to the even sum does not change. You only need to account for the one element that moved.

There are four cases to consider. If the old value was even and the new value is even, you subtract the old and add the new. If the old value was even and the new value is odd, you just subtract the old. If the old value was odd and the new value is even, you just add the new. If the old value was odd and the new value is odd, the even sum does not change at all.

Walking through it step by step

Let's trace through nums = [1, 2, 3, 4] with queries = [[1,0], [-3,1], [-4,0], [2,3]]. We start by computing the initial even sum: 2 + 4 = 6.

The final answer is [8, 6, 2, 4]. Each step only examined the single element that changed, not the entire array. Five steps (one initial scan plus four O(1) updates) instead of four full-array scans.

The incremental solution

def sumEvenAfterQueries(nums, queries):
    even_sum = sum(x for x in nums if x % 2 == 0)
    answer = []
    for val, index in queries:
        if nums[index] % 2 == 0:
            even_sum -= nums[index]
        nums[index] += val
        if nums[index] % 2 == 0:
            even_sum += nums[index]
        answer.append(even_sum)
    return answer

Here is what each piece does:

1. Compute the initial even_sum by scanning the array once. This is O(n) and only happens once.
2. For each query, check if the current value at nums[index] is even. If so, remove it from even_sum because the value is about to change.
3. Apply the update: nums[index] += val.
4. Check if the updated value is even. If so, add it to even_sum.
5. Append the current even_sum to the answer list.

Complexity analysis

The initial scan takes O(n). Each of the q queries takes O(1) to process. The output array has q elements. No additional data structures are needed beyond the running sum variable.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Running aggregate under point updates

The pattern of maintaining a derived value (sum, count, max) as individual elements change:

aggregate = compute_initial(data)
for update in updates:
    undo_old_contribution(aggregate, data[update.index])
    apply_update(data, update)
    add_new_contribution(aggregate, data[update.index])

In Sum of Even Numbers After Queries, the aggregate is the even sum and the contribution check is whether a value is even. In problems like range sum queries with point updates, the aggregate is the total sum and every element contributes. The skeleton is the same: undo the old, apply the change, redo the new.

2. Parity-based filtering

The pattern of treating elements differently based on whether they are even or odd:

for value in data:
    if value % 2 == 0:
        process_even(value)
    else:
        process_odd(value)

In this problem, parity determines whether a value contributes to the running sum. In problems like Sort Array By Parity, parity determines placement. In problems involving bitwise operations, parity of specific bits drives the logic. The core mechanic is the same: branch on value % 2 and handle each case.

Edge cases

Before submitting, make sure your solution handles these:

• All values already even nums = [2, 4, 6]: the initial even sum includes everything. Each query adjusts from a fully even starting point.
• All values odd nums = [1, 3, 5]: the initial even sum is 0. Only queries that make a value even will increase the sum.
• Negative even values nums = [-2, -4]: negative even numbers still count toward the even sum. Make sure your parity check works with negatives (it does, since (-2) % 2 == 0 in Python).
• Query makes no parity change adding 2 to an even number keeps it even. The sum changes by the added value, not by the full new value.
• Query toggles parity twice if you process the same index in consecutive queries, the element might flip from even to odd and back. The incremental approach handles this naturally.
• Single element array nums = [0]: only one element to track. The even sum is either that element (if even) or 0.

Common mistakes

1. Forgetting to subtract the old value before the update. If you only add the new value when it is even, you double-count elements that were already even before the query. You must first check and subtract the old value if it was even, then apply the update, then check and add the new value.

2. Checking parity of val instead of nums[index]. The query value val is what you add, but parity depends on the resulting nums[index], not on val itself. Adding an odd number to an odd number gives an even result. You need to check the actual element, not the delta.

3. Recomputing the full even sum each iteration. This is the brute force trap. It produces correct results but runs in O(n * q) instead of O(n + q). For large inputs, this times out.

4. Modifying nums[index] before subtracting the old contribution. The order matters. If you add val to nums[index] first, you have lost the old value and cannot undo its contribution to the even sum correctly.

From understanding to recall

You have read the incremental approach and it makes sense. Subtract the old contribution if it was even, apply the update, add the new contribution if it is even. Three lines inside the loop. Clean and fast.

But in an interview, the pressure makes it easy to mix up the order of operations, forget to check parity before the update, or accidentally recompute the sum from scratch. These mistakes are not about understanding. They are about recall under pressure.

Spaced repetition fixes this. You practice writing the incremental even sum loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "maintain a sum under point updates" and the code flows out: check old, update, check new. No hesitation.

The running aggregate pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Subarray Sum Equals K - Another array problem where maintaining a running sum avoids brute force rescanning
• Contiguous Array - Prefix sums with parity-based reasoning (counting 0s and 1s as -1 and +1)
• Degree of an Array - Tracking array properties incrementally using hash maps

CodeBricks breaks the sum of even numbers after queries LeetCode problem into its incremental aggregate and parity filtering building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When an incremental update question shows up in your interview, you do not think about it. You just write it.