Handling Sum Queries After Update - Practice Coding Problems

Handling Sum Queries After Update - Problem

You are given two 0-indexed arrays nums1 and nums2 and a 2D array queries of queries. There are three types of queries:

Type 1: queries[i] = [1, l, r]. Flip the values from 0 to 1 and from 1 to 0 in nums1 from index l to index r (both inclusive).

Type 2: queries[i] = [2, p, 0]. For every index 0 <= i < n, set nums2[i] = nums2[i] + nums1[i] * p.

Type 3: queries[i] = [3, 0, 0]. Find the sum of all elements in nums2.

Return an array containing all the answers to the third type queries.

Input & Output

Example 1 — Basic Operations

$ Input: nums1 = [1,0,1], nums2 = [0,0,0], queries = [[1,1,1],[2,1,0],[3,0,0]]

› Output: [3]

💡 Note: Query [1,1,1]: flip nums1[1] from 0→1, so nums1=[1,1,1]. Query [2,1,0]: add nums1[i]*1 to nums2[i], so nums2=[1,1,1]. Query [3,0,0]: sum of nums2 = 1+1+1 = 3.

Example 2 — Multiple Sum Queries

$ Input: nums1 = [1,0,1,0], nums2 = [1,2,3,4], queries = [[3,0,0],[2,3,0],[3,0,0],[1,0,3],[3,0,0]]

› Output: [10,16,13]

💡 Note: Initial sum=10. After [2,3,0]: add 2*3=6, sum=16. After [1,0,3]: flip all bits, nums1=[0,1,0,1], nums2 unchanged, sum=16. But wait - we need to track changes properly.

Example 3 — Range Flip Edge Case

$ Input: nums1 = [1], nums2 = [5], queries = [[2,2,0],[3,0,0],[1,0,0],[2,3,0],[3,0,0]]

› Output: [7,7]

💡 Note: [2,2,0]: nums2[0] += 1*2 = 7. [3,0,0]: sum=7. [1,0,0]: flip nums1[0] to 0. [2,3,0]: add 0*3=0. [3,0,0]: sum=7.

Constraints

1 ≤ nums1.length, nums2.length ≤ 10⁵
0 ≤ nums1[i] ≤ 1
1 ≤ nums2[i] ≤ 10⁹
1 ≤ queries.length ≤ 10⁵
queries[i].length == 3
1 ≤ queries[i][0] ≤ 3
For queries of type 1: 0 ≤ l ≤ r < nums1.length
For queries of type 2: 1 ≤ p ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

nums1 (binary), nums2 (integers), queries

Query Processing

Type 1: flip bits, Type 2: bulk update, Type 3: sum

Output

Array of sums from type 3 queries

Key Takeaway

🎯 Key Insight: Track the count of 1s in nums1 instead of processing individual elements for type 2 queries

Asked in

G Google 8 a Amazon 5 M Microsoft 3

The key insight is to avoid recalculating the entire nums2 array for type 2 queries by tracking only the count of 1s in nums1 and maintaining the sum of nums2. Best approach uses count-based optimization for O(1) type 2 and type 3 queries. Time: O(q × n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(q × n)	O(1)	Process each query directly with array operations
Count-Based Optimization	O(q × n)	O(1)	Track only the count of 1s in nums1 instead of individual bits

Brute Force — Algorithm Steps

Step 1: For type 1 queries, flip each element in the range [l, r] of nums1
Step 2: For type 2 queries, iterate through all elements and update nums2[i] += nums1[i] * p
Step 3: For type 3 queries, sum all elements in nums2 and add to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Query 1

Flip bits in range [1,1] of nums1

Query 2

Add nums1[i] * 1 to each nums2[i]

Query 3

Sum all elements in nums2

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long* solution(int* nums1, int nums1Size, int* nums2, int nums2Size, int** queries, int queriesSize, int* returnSize) {
    long long* result = (long long*)malloc(queriesSize * sizeof(long long));
    *returnSize = 0;
    
    for (int i = 0; i < queriesSize; i++) {
        if (queries[i][0] == 1) {  // Flip range in nums1
            int l = queries[i][1], r = queries[i][2];
            for (int j = l; j <= r; j++) {
                nums1[j] = 1 - nums1[j];
            }
        } else if (queries[i][0] == 2) {  // Update nums2
            int p = queries[i][1];
            for (int j = 0; j < nums2Size; j++) {
                nums2[j] += nums1[j] * p;
            }
        } else {  // queries[i][0] == 3, sum nums2
            long long sum = 0;
            for (int j = 0; j < nums2Size; j++) {
                sum += nums2[j];
            }
            result[(*returnSize)++] = sum;
        }
    }
    
    return result;
}

int main() {
    // Simplified for demonstration
    int nums1[] = {1, 0, 1};
    int nums2[] = {0, 0, 0};
    int* queryData[] = {(int[]){1,1,1}, (int[]){2,1,0}, (int[]){3,0,0}};
    int** queries = queryData;
    int returnSize;
    
    long long* result = solution(nums1, 3, nums2, 3, queries, 3, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%lld", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q × n)

q queries, each type 1 and type 2 query can take O(n) time, type 3 takes O(n)

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

12.8K Views

Medium Frequency

~35 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler