### LIT2021015_AYUSH's blog

By LIT2021015_AYUSH, history, 3 weeks ago,

Here we are given an array of size n (n<=1e5) and we are given to process q (q<=1e5) queries. Queries are of two types .The first one is a point update query. The second one tell us to calculate sum of all subarrays in the range (l to r) . More formarlly in second type of query we are given l and r and we have to find Σf(i,j) where l<=i<=j<=r and f(i,j) denotes the sum of subarray starting at i th index and ending at j th index.

Although I tried it using segment Tree but couldn't think of the optimal approach for this.

• -2

 » 3 weeks ago, # |   0 this came in my google oa, someone already posted editorial of it on hackerearth:https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/range-function-4-18b4a425/editorial/
•  » » 3 weeks ago, # ^ |   0 Ya it also came in my google OA on 13th . But I wondered how to solve it.Anyways, Thanks for sharing the editorial link.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Same ,the solution gave me a TLE even after using st. Any other approach to solve it ?
 » 3 weeks ago, # |   0 Don't know why people downvote the blogs even after asking legit questions and that too after the contests.
 » 3 weeks ago, # |   0 say you want to merge [l1,r1] and [l2,r2] in seg tree then extra contribution of any element at index i in first range would be i*(r2-l2+1)*a[i] similarily for second range , so you just need summation of i*a[i] to merge intervals , you can use prefix sum to find it giving o(1) complexity for merging