### pH7's blog

By pH7, history, 5 weeks ago, ,

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]

• 0

 » 5 weeks ago, # |   +3 Auto comment: topic has been updated by pH7 (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 Use a segment tree: Segment tree — cp-algorithms
•  » » 5 weeks ago, # ^ |   0 If we want range sum then lazy segment tree is a solution, but how to handle updates lazily if we want range multiplication?
 » 5 weeks ago, # |   -10 Where do you see a multiplication there? "...which is the sum of all the..."
•  » » 5 weeks ago, # ^ |   +3 I am asking what to do if there is multiplication!
•  » » » 5 weeks ago, # ^ |   -18 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.
•  » » » » 5 weeks ago, # ^ |   0 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?
 » 5 weeks ago, # |   0 Can we even handle updates with segment tree?
 » 5 weeks ago, # | ← Rev. 2 →   0 Similar to a problem in the ongoing Long challenge. I hope this is just a coincidence.WEIRDMUL
 » 5 weeks ago, # |   +8 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.
•  » » 5 weeks ago, # ^ |   0 f(x) = log(x) Thought of it :) Thank you!
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 pH7 were you able to figure out the addition part?
•  » » » » 4 weeks ago, # ^ |   0 No :(