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