For example, given an array A of length n and m queries. Each query gives an interval [l,r] and you need to calculate. . How to solve this problem in O(n+m)?We can calculate the prefix sum array B in which Bi is equal to. . And for each query, the answer is Br-Bl-1.Since Rikka is interested in this powerful trick, she sets a simple task about Prefix Sum for you:. Given two integers n,m, Rikka constructs an array A of length n which is initialized by Ai = 0. And then she makes m operations on it.
Prefix Sum is a useful trick in data structure problems. For example, given an array A of length n and m queries. Each query gives an interval [l,r] and you need to calculate sum_{i=l}^r A_i ∑ i=l r A i . How to solve this problem in O(n+m)? We can calculate the prefix sum array B in which Bi is equal to sum_{j=1}^i A_i ∑ j=1 i A i . And for each query, the answer is Br-Bl-1. Since Rikka is interested in this powerful trick, she sets a simple task about Prefix Sum for you: Given two integers n,m, Rikka constructs an array A of length n which is initialized by Ai = 0. And then she makes m operations on it. There are three types of operations: 1. 1 L R w, for each index i ∈ [L,R], change Ai to Ai + w. 2. 2, change A to its prefix sum array. i.e., let A' be a back-up of A, for each i ∈ [1,n], change Ai to . 3. 3 L R, query for the interval sum sum_{i=L}^R A_i ∑ i=L R A i .
