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.
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/
Ya it also came in my google OA on 13th . But I wondered how to solve it.Anyways, Thanks for sharing the editorial link.
Same ,the solution gave me a TLE even after using st. Any other approach to solve it ?
Don't know why people downvote the blogs even after asking legit questions and that too after the contests.
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