Update range using static array for each query

Правка en3, от Lakh, 2021-05-26 11:05:20

Today I was thinking of a problem where we are given a static array like a=[1,1,3]. Now we have another array which is initially filled with zero and it's size is > 3 . Let's say 10. Now suppose we have Q queries and each query contains range [L,R] of length = 3 (i.e. R-L+1==3). Now for each of these ranges we we have to add the array a=[1,1,3]. Finally we have to output the resulting new array formed.

For e.g. a=[1,1,3], b(initially zeros) = [0,0,0,0,0]

Queries : (0,2) -> updates = [0,0,0,0,0]-> [1,1,3,0,0]
          (1,3) -> updates = [1,1,3,0,0] -> [1,2,4,3,0] ( Added [1,1,3] to the array from indices 1 to index 3)

Final output : [1,2,4,3,0]

Not sure about the constraints part.

I am thinking if it's possible to apply segment trees here but still no progress. Is it possible to solve such a problem using segment trees?? Looking towards some ideas for solving this kind of range update operation. Thank you in advance :)

Теги #segment tree, range-update, #arrays

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Lakh 2021-05-26 11:05:20 20
en2 Английский Lakh 2021-05-26 10:52:15 22
en1 Английский Lakh 2021-05-26 10:50:50 999 Initial revision (published)