pH7's blog

How to solve this?
By pH7, history, 4 years ago, In English

Hi all! I was wondering about solution if in Spoj HORRIBLE we are required to get range multiplication instead of range sum. So basically how can we solve below problem ?

Given an array of N elements handle below two type of range queries. - Update L R v : Add v to each element in range [L, R] - Query L R : Get multiplication of each element in range [L, R]

I am out of ideas. Please help!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by pH7 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Use a segment tree: Segment tree — cp-algorithms

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

    If we want range sum then lazy segment tree is a solution, but how to handle updates lazily if we want range multiplication?

    → Reply
»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Where do you see a multiplication there? "...which is the sum of all the..."

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I am asking what to do if there is multiplication!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      Ah, ok.

      I think we would store the added value like in case the cumulative function was addition. But on query we cannot simply add the value, but we have to multiply by x^segsize and multiply with this.

      The push down works like it was addition, too.

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

        Sorry, i didn't quite get it! Let say A = {1, 4, 6} Consider L = 1 R = 3 Query : 24 Update 1 : {2, 5, 7} Query : 70 Can you please explain with this example?

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we even handle updates with segment tree?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Similar to a problem in the ongoing Long challenge. I hope this is just a coincidence.

WEIRDMUL

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

If you want to have multiplication instead of sum, think of replacing each $$$x$$$ in the array with some $$$f(x)$$$, such that $$$f(xy) = f(x) + f(y)$$$. Then, by calculating sum of $$$f(x_i)$$$ in some range, you will in fact calculate $$$f(\Pi{x_i})$$$ in the range. But the addition to the range in this case would not be possible -- instead, such problem would probably require multiplication of all numbers in the range by some v.

→ Reply