LIT2021015_AYUSH's blog

Needed Help with a problem I m stuck on.
By LIT2021015_AYUSH, history, 2 months ago, In English

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.

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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/

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ya it also came in my google OA on 13th . But I wondered how to solve it.Anyways, Thanks for sharing the editorial link.

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Same ,the solution gave me a TLE even after using st. Any other approach to solve it ?

      → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Don't know why people downvote the blogs even after asking legit questions and that too after the contests.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply