Блог пользователя Lakh

Update range using static array for each query
Автор Lakh, история, 3 года назад, По-английски

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 :)

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I hope this could help: https://cses.fi/problemset/task/1736

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 ??

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • Every time there is a query with $$$l = k$$$, we add $$$A[0]$$$ to $$$C[k]$$$
  • Every time there is a query with $$$l = k - 1$$$, we add $$$A[1]$$$ to $$$C[k]$$$
  • Every time there is a query with $$$l = k - 2$$$, we add $$$A[2]$$$ to $$$C[k]$$$
  • etc.

We arrive at the formula

$$$C[k] = A[0] B[k] + A[1] B[k - 1] + A[2] B[k - 2] + \cdots = \sum_{i + j = k} A[i] B[j].$$$

We are given arrays $A$ and $$$B$$$ and want to calculate the formula above for each $$$k$$$. This is precisely the problem FFT solves.

→ Ответить