Handling Sum Queries After Update solution and explanation
5 more videos on this problem
Handling Sum Queries After Update || Leetcode-2569 || C++, Java & PythonAryan Mittal · 26:29 · 1K views
Leetcode Biweekly Contest 98 | Handling Sum Queries After Update | PythonBayu Aji · 3:19 · 496 views
【每日一题】LeetCode 2569. Handling Sum Queries After UpdateHuifeng Guan · 29:29 · 445 views
2569. Handling Sum Queries After Update (Leetcode Hard)Programming Live with Larry · 1:39:19 · 354 views
HANDLING SUM QUERIES AFTER UPDATE | Leetcode 2569 | LAZY PROPOGATION | SEGMENT TREE CONCEPTS |proteinCoder · 10:47 · 72 views
6358. Handling Sum Queries After Update Leetcode Solution LOGIC JAVA/CPP/ PYTHONCodeStruggle · 0:38 · 62 views
The problem
You are given two 0-indexed arrays nums1 and nums2 and a 2D array queries of queries. There are three types of queries:
- For a query of type 1,
queries[i] = [1, l, r]. Flip the values from0to1and from1to0innums1from indexlto indexr. Bothlandrare 0-indexed. - For a query of type 2,
queries[i] = [2, p, 0]. For every index0 <= i < n, setnums2[i] = nums2[i] + nums1[i] * p. - For a query of type 3,
queries[i] = [3, 0, 0]. Find the sum of the elements innums2.
Return an array containing all the answers to the third type queries.
Example 1:
Input: nums1 = [1,0,1], nums2 = [0,0,0], queries = [[1,1,1],[2,1,0],[3,0,0]] Output: [3] Explanation: After the first query nums1 becomes [1,1,1]. After the second query, nums2 becomes [1,1,1], so the answer to the third query is 3. Thus, [3] is returned.
Example 2:
Input: nums1 = [1], nums2 = [5], queries = [[2,0,0],[3,0,0]] Output: [5] Explanation: After the first query, nums2 remains [5], so the answer to the second query is 5. Thus, [5] is returned.
Constraints:
1 <= nums1.length,nums2.length <= 105nums1.length = nums2.length1 <= queries.length <= 105queries[i].length = 30 <= l <= r <= nums1.length - 10 <= p <= 1060 <= nums1[i] <= 10 <= nums2[i] <= 109
Approach overview
Problem Overview: You maintain two arrays. Queries flip bits in nums1, add a multiple of the number of ones in nums1 to nums2, or ask for the total sum of nums2. The challenge is handling frequent range updates and keeping the count of ones available instantly for later queries.
Approach 1: Naive Iterative Approach (O(n) per update, O(q·n) overall)
The straightforward method directly applies each query. For a flip operation, iterate through the specified range in nums1 and toggle each bit. For the second query type, count the number of ones in nums1 by iterating through the array, then add p * ones to a running total of nums2. This approach relies purely on array traversal using basic operations on an array. It works for small inputs but becomes too slow when both the array size and number of queries grow large.
Approach 2: Segment Tree Optimization for Range Updates (O((n + q) log n) time, O(n) space)
The optimized approach stores the count of ones in nums1 using a segment tree. Each node tracks how many ones exist in its range. When a query flips a range, instead of updating each element individually, the tree performs a lazy range flip: the stored count becomes segment_length - current_ones. Lazy propagation postpones updates to children until necessary, keeping operations efficient.
For the second query type, the algorithm reads the total number of ones directly from the root of the tree in O(1). Multiply that value by p and add it to a running sum representing the total of nums2. Since the problem only asks for the sum of nums2, there is no need to update each element individually. The third query simply outputs this stored sum. This design converts expensive full-array operations into logarithmic updates and constant-time queries.
Recommended for interviews: Interviewers expect the Segment Tree with lazy propagation solution. The brute-force iteration shows you understand the mechanics of the queries, but it does not scale. Using a segment tree to maintain the number of ones while supporting fast range flips demonstrates strong knowledge of range query data structures.
Approach 1: Naive Iterative Approach
This approach involves diving directly into the queries and processing them straightforwardly. We iterate through the queries and process each based on their type. This is simple to implement but not optimized for large input sizes, particularly for type 1 queries which require range flips.
def handleQueriesNaive(nums1, nums2, queries):
results = []
for query in queries:
type = query[0]
l = query[1]
r = query[2]
if type == 1:
for i in range(l, r + 1):
nums1[i] = 1 - nums1[i]
elif type == 2:
for i in range(len(nums2)):
nums2[i] += nums1[i] * l
elif type == 3:
results.append(sum(nums2))
return resultsimport java.util.*;
public class Solution {
public List<Integer> handleQueriesNaive(int[] nums1, int[] nums2, int[][] queries) {
List<Integer> results = new ArrayList<>();
for (int[] query : queries) {
int type = query[0], l = query[1], r = query[2];
if (type == 1) {
for (int i = l; i <= r; ++i) {
nums1[i] = 1 - nums1[i];
}
} else if (type == 2) {
for (int i = 0; i < nums2.length; ++i) {
nums2[i] += nums1[i] * l;
}
} else if (type == 3) {
int sum = 0;
for (int num : nums2) sum += num;
results.add(sum);
}
}
return results;
}
}#include <iostream>
#include <vector>
using namespace std;
void flip(vector<int>& nums1, int l, int r) {
for (int i = l; i <= r; i++) {
nums1[i] = 1 - nums1[i];
}
}
vector<int> handleQueriesNaive(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
vector<int> results;
for (auto& query : queries) {
int type = query[0], l = query[1], r = query[2];
if (type == 1) {
flip(nums1, l, r);
} else if (type == 2) {
for (int i = 0; i < nums2.size(); ++i) {
nums2[i] += nums1[i] * l;
}
} else if (type == 3) {
results.push_back(accumulate(nums2.begin(), nums2.end(), 0));
}
}
return results;
}function handleQueriesNaive(nums1, nums2, queries) {
const results = [];
for (const query of queries) {
const [type, l, r] = query;
if (type === 1) {
for (let i = l; i <= r; i++) {
nums1[i] = 1 - nums1[i];
}
} else if (type === 2) {
for (let i = 0; i < nums2.length; i++) {
nums2[i] += nums1[i] * l;
}
} else if (type === 3) {
results.push(nums2.reduce((a, b) => a + b, 0));
}
}
return results;
}#include <stdio.h>
#include <stdlib.h>
void flip(int* nums1, int l, int r) {
for (int i = l; i <= r; ++i) {
nums1[i] = 1 - nums1[i];
}
}
int* handleQueriesNaive(int* nums1, int nums1Size, int* nums2, int nums2Size, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
int* results = malloc(queriesSize * sizeof(int));
*returnSize = 0;
for (int i = 0; i < queriesSize; ++i) {
int type = queries[i][0];
int l = queries[i][1];
int r = queries[i][2];
if (type == 1) {
flip(nums1, l, r);
} else if (type == 2) {
for (int j = 0; j < nums2Size; j++) {
nums2[j] += nums1[j] * l;
}
} else if (type == 3) {
int sum = 0;
for (int j = 0; j < nums2Size; j++) {
sum += nums2[j];
}
results[(*returnSize)++] = sum;
}
}
return results;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> HandleQueriesNaive(int[] nums1, int[] nums2, int[][] queries) {
List<int> results = new List<int>();
foreach (var query in queries) {
int type = query[0], l = query[1], r = query[2];
if (type == 1) {
for (int i = l; i <= r; ++i) {
nums1[i] = 1 - nums1[i];
}
} else if (type == 2) {
for (int i = 0; i < nums2.Length; ++i) {
nums2[i] += nums1[i] * l;
}
} else if (type == 3) {
int sum = 0;
foreach (var num in nums2) sum += num;
results.Add(sum);
}
}
return results;
}
}Python's simplicity allows for a concise implementation following the same logic as the previous languages. We leverage list operations and comprehensions for clarity and efficiency.
Time Complexity: O(n * m) overall, due to potential repeated iteration for range modification.
Space Complexity: O(1) for in-place modifications, with O(q) for output storage.
Approach 2: Segment Tree Optimization for Range Updates
Using a Segment Tree allows us to efficiently handle range updates, particularly suitable for type 1 queries that require flipping elements over a range. This optimization ensures that updates and queries are both handled in logarithmic time.
#include <iostream>
#include <vector>
using namespace std;
class SegmentTree {
vector<int> tree, lazy;
int n;
void build(const vector<int>& nums1, int node, 0, int end) {
if (start == end) {
tree[node] = nums1[start];
} else {
int mid = (start + end) / 2;
build(nums1,2 * node + 1, start, mid);
build(nums1,2 * node + 2, mid + 1, end);
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
}
void updateRangeUtil(int node, int start, int end, int l, int r, int val) {
if (lazy[node] != 0) {
tree[node] = (end - start + 1) - tree[node];
if (start != end) {
lazy[node * 2 + 1] ^= 1;
lazy[node * 2 + 2] ^= 1;
}
lazy[node] = 0;
}
if (start > end || start > r || end < l)
return;
if (start >= l && end <= r) {
tree[node] = (end - start + 1) - tree[node];
if (start != end) {
lazy[node * 2 + 1] ^= 1;
lazy[node * 2 + 2] ^= 1;
}
return;
}
int mid = (start + end) / 2;
updateRangeUtil(node * 2 + 1, start, mid, l, r, val);
updateRangeUtil(node * 2 + 2, mid + 1, end, l, r, val);
tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];
}
public:
SegmentTree(const vector<int>& nums1) : n(nums1.size()) {
tree.resize(4 * n);
lazy.resize(4 * n);
build(nums1, 0, 0, n - 1);
}
void updateRange(int l, int r, int val) {
updateRangeUtil(0, 0, n - 1, l, r, val);
}
int querySum() {
return tree[0];
}
};
vector<int> handleQueriesSegmentTree(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
int n = nums1.size();
SegmentTree st(nums1);
vector<int> results;
for (auto& query : queries) {
int type = query[0], l = query[1], r = query[2];
if (type == 1) {
st.updateRange(l, r, 1);
} else if (type == 2) {
int totalOnes = st.querySum();
for (int i = 0; i < n; ++i) {
nums2[i] += (nums1[i] * totalOnes);
}
} else if (type == 3) {
results.push_back(accumulate(nums2.begin(), nums2.end(), 0));
}
}
return results;
}This solution uses a Segment Tree to manage range updates efficiently. The segment tree supports lazy propagation, which allows us to update ranges of nums1 in logarithmic time. We utilize the tree to keep track of the number of ones in any segment, which is used when applying type 2 queries.
Time Complexity: O(log n) per update and query on the segment tree, much improved for large ranges.
Space Complexity: O(n) for the segment tree structure.
Approach 3: Segment Tree
According to the problem description:
- Operation
1is to reverse all numbers in the index range[l,..r]of arraynums1, that is, change0to1and1to0. - Operation
3is to sum all numbers in arraynums2. - Operation
2is to add the sum of all numbers in arraynums2withptimes the sum of all numbers in arraynums1, that is,sum(nums2) = sum(nums2) + p * sum(nums1).
Therefore, we actually only need to maintain the segment sum of array nums1, which can be implemented through a segment tree.
We define each node of the segment tree as Node, each node contains the following attributes:
l: The left endpoint of the node, the index starts from1.r: The right endpoint of the node, the index starts from1.s: The segment sum of the node.lazy: The lazy tag of the node.
The segment tree mainly has the following operations:
build(u, l, r): Build the segment tree.pushdown(u): Propagate the lazy tag.pushup(u): Update the information of the parent node with the information of the child nodes.modify(u, l, r): Modify the segment sum. In this problem, it is to reverse each number in the segment, so the segment sums = r - l + 1 - s.query(u, l, r): Query the segment sum.
First, calculate the sum of all numbers in array nums2, denoted as s.
When executing operation 1, we only need to call modify(1, l + 1, r + 1).
When executing operation 2, we update s = s + p times query(1, 1, n).
When executing operation 3, we just need to add s to the answer array.
The time complexity is O(n + m times log n), and the space complexity is O(n). Where n and m are the lengths of arrays nums1 and queries respectively.
type node struct {
l, r, s, lazy int
}
type segmentTree struct {
nums []int
tr []*node
}
func newSegmentTree(nums []int) *segmentTree {
n := len(nums)
tr := make([]*node, n<<2)
for i := range tr {
tr[i] = &node{}
}
t := &segmentTree{nums, tr}
t.build(1, 1, n)
return t
}
func (t *segmentTree) build(u, l, r int) {
t.tr[u].l, t.tr[u].r = l, r
if l == r {
t.tr[u].s = t.nums[l-1]
return
}
mid := (l + r) >> 1
t.build(u<<1, l, mid)
t.build(u<<1|1, mid+1, r)
t.pushup(u)
}
func (t *segmentTree) modify(u, l, r int) {
if t.tr[u].l >= l && t.tr[u].r <= r {
t.tr[u].lazy ^= 1
t.tr[u].s = t.tr[u].r - t.tr[u].l + 1 - t.tr[u].s
return
}
t.pushdown(u)
mid := (t.tr[u].l + t.tr[u].r) >> 1
if l <= mid {
t.modify(u<<1, l, r)
}
if r > mid {
t.modify(u<<1|1, l, r)
}
t.pushup(u)
}
func (t *segmentTree) query(u, l, r int) int {
if t.tr[u].l >= l && t.tr[u].r <= r {
return t.tr[u].s
}
t.pushdown(u)
mid := (t.tr[u].l + t.tr[u].r) >> 1
res := 0
if l <= mid {
res += t.query(u<<1, l, r)
}
if r > mid {
res += t.query(u<<1|1, l, r)
}
return res
}
func (t *segmentTree) pushup(u int) {
t.tr[u].s = t.tr[u<<1].s + t.tr[u<<1|1].s
}
func (t *segmentTree) pushdown(u int) {
if t.tr[u].lazy == 1 {
mid := (t.tr[u].l + t.tr[u].r) >> 1
t.tr[u<<1].s = mid - t.tr[u].l + 1 - t.tr[u<<1].s
t.tr[u<<1].lazy ^= 1
t.tr[u<<1|1].s = t.tr[u].r - mid - t.tr[u<<1|1].s
t.tr[u<<1|1].lazy ^= 1
t.tr[u].lazy ^= 1
}
}
func handleQuery(nums1 []int, nums2 []int, queries [][]int) (ans []int64) {
tree := newSegmentTree(nums1)
var s int64
for _, x := range nums2 {
s += int64(x)
}
for _, q := range queries {
if q[0] == 1 {
tree.modify(1, q[1]+1, q[2]+1)
} else if q[0] == 2 {
s += int64(q[1] * tree.query(1, 1, len(nums1)))
} else {
ans = append(ans, s)
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Iterative Approach | Time Complexity: O(n * m) overall, due to potential repeated iteration for range modification. |
| Segment Tree Optimization for Range Updates | Time Complexity: O(log n) per update and query on the segment tree, much improved for large ranges. |
| Segment Tree | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Iterative Approach | O(q · n) | O(1) | Small arrays or when implementing a quick baseline solution |
| Segment Tree with Lazy Propagation | O((n + q) log n) | O(n) | Large input sizes with many range flips and queries |
Frequently asked questions
Is Handling Sum Queries After Update easy or hard?
Handling Sum Queries After Update is classified as a Hard problem on LeetCode. The difficulty comes from combining range updates, lazy propagation, and query optimization while avoiding repeated full-array operations.
Handling Sum Queries After Update Python/Java solution
Implement the optimized solution by building a segment tree that stores the count of ones for each range. Range flip operations use lazy propagation, and a variable tracks the running sum of nums2. The same logic translates cleanly to Python, Java, and C++ implementations.
What is the best approach for Handling Sum Queries After Update?
The most efficient solution uses a Segment Tree with lazy propagation to track the number of ones in nums1. Range flip operations update the tree in O(log n), and the total count of ones is always available at the root. This allows type‑2 queries to update the sum in constant time.
How to solve Handling Sum Queries After Update in O((n+q) log n)?
Build a segment tree over nums1 that stores the count of ones in each segment. Use lazy propagation to flip bits in a range efficiently by converting the stored count to segment_length minus current_ones. Maintain a running sum of nums2 and update it using the ones count whenever a type‑2 query appears.
Is Handling Sum Queries After Update asked at Google/Amazon/Meta?
Problems involving segment trees and lazy propagation frequently appear in interviews at companies like Google, Amazon, and Meta. This specific pattern—range updates combined with aggregate queries—is a classic advanced data structure interview topic.
What data structure is used in Handling Sum Queries After Update?
The key data structure is a Segment Tree with lazy propagation. It efficiently handles range bit flips while maintaining the count of ones needed to compute updates to the total sum of nums2.
What is the time complexity of Handling Sum Queries After Update?
The optimal approach runs in O((n + q) log n) time using a segment tree. Each range flip update takes O(log n), while reading the total number of ones and processing sum queries is O(1). Space complexity is O(n) for the tree structure.