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 :)
I hope this could help: https://cses.fi/problemset/task/1736
Thanks for sharing this problem. However in the cses problem we have to add some fixed array like [1,2,3,4..]. But suppose our static array is like [1,0,4] then how to solve this ??
oh so that's what you mean, I thought otherwise by looking at the inputs, my bad
I haven't really thought much at all, but since the size is fixed, you can probably try something like updating just the beginning, then process the rest later or something?
Do I understand correctly that you only ask for the final array (i.e. there are only update queries and no queries about the intermediate states of the array)? Also, do I understand correctly that $$$r - l + 1$$$ will always be the length of the array? In this case, I have a solution.
Denote by $$$A$$$ the static array that you add, by $$$B[j]$$$ the number of times we had a query with $$$l = j$$$, and by $$$C$$$ the final array that we need to find. Now, let's think about how $$$C[k]$$$ is formed.
We arrive at the formula
We are given arrays $A$ and $$$B$$$ and want to calculate the formula above for each $$$k$$$. This is precisely the problem FFT solves.