Data Structures19 sections · 729 units
Open in Course

Problem - Range Sum Queries I

Basic sqrt decomposition

You're given an array of nn integers and qq queries. Each query is either:

1.1. Update: set arr[i]=varr[i] = v

2.2. Query: return sum(l,r)sum(l, r) Constraints: n,q2105n, q \leq 2 \cdot 10^5. You're solving the classic problem for sqrt decomposition. Before reading the solution, think about whether segment trees or sqrt decomposition would be better here. What's the tradeoff?