Array with queries to decrement or find sum of range

Question

I have been given an array of integers of size n and q queries which can be of 2 types:
1.Decrement all elements in the given range by some value
2.Find sum of all elements in the given range
1<=n,q<=10^5
I have tried brute force but it gives TLE
Same goes for prefix sum and even segment trees which improve sum query but slow down updation
I cannot figure out how to update in O(log n)
Would lazy propagation help ?
If not , how else can i proceed with this?
P.S. First timer here . Apologies if i missed out on something

Answer 1

Suppose that your array is $a_1,\ldots,a_n,ドル but instead of storing it this way, you store the differences $\delta_i = a_i - a_{i-1}$ (where $a_0 = 0$). Decrementing $a_i,\ldots,a_j$ by $x$ is then the same as decrementing $\delta_i$ by $x$ and incrementing $\delta_{j+1}$ by $x$. Querying the prefix sum $a_1 + \cdots + a_j$ (using which you can query the sum of any range) amounts to calculating $$ \sum_{t=1}^j \sum_{k=1}^t \delta_k = \sum_{k=1}^j \sum_{t=k}^j \delta_k = \sum_{k=1}^j (j-k+1)\delta_k = (j+1)\sum_{k=1}^j \delta_k - \sum_{k=1}^j k\delta_k. $$ The idea now is to use a Fenwick tree, which is an array data structure which can perform both element updates and prefix sums in $O(\log n)$. We use two Fenwick trees, one storing $\delta_1,\ldots,\delta_n$ and the other storing $\delta_1,2\delta_2,\ldots,n\delta_n$ (we can in fact merge them into a single Fenwick tree which stores information for both values at every node). Above we have outlined how to perform each of your two queries in $O(\log n)$.