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!

Auto comment: topic has been updated by pH7 (previous revision, new revision, compare).Use a segment tree: Segment tree — cp-algorithms

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

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

I am asking what to do if there is multiplication!

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.

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?

Can we even handle updates with segment tree?

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

WEIRDMUL

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.

f(x) = log(x) Thought of it :) Thank you!

pH7 were you able to figure out the addition part?

No :(