Problem - A to B | Practice Problems
I am trying to solve this question but i cannot get an AC solution to it. I tried solving it but was giving me TLE.
I checked on editorial but it was missing, just the solution is given.
Thanks in advance 
1 Like
At first maintain the product of entire array A. Whenever the query is 1 just multiply the multiplicative modulo inverse of A[id] With 1e9+7 to the product.
Whenever the query is 0 , multiply the multiplicative modulo inverse of A[id] With 1e9+7 to the product and also multiply the product with the new value V.
Always take care of taking mod of product with 1e9 + 7.
Use Fermat’s Little Theorem.
Remember maintaing product of the array A once will suffice.
Thanks.
1 Like
Above solution will work fine but you have to tackle with modulo multiplication inverse.
You can solve this problem using Segment Tree, you just need to build segment tree for multiplication with mod 1e9+7.
for query 0, you just need to update the segment tree with given value
for query 1, you need to find the multiplication of range [1, ID - 1] and [ID + 1, N] and then multiply them and take mod 1e9+7 will give you the answer ; P
1 Like
Segment Tree is overkill. There is a trade-off between implementation time and execution time, while Segment Tree does not provide any betterment over the later, it is horrible at the former. Not to mention it requires 4*size of input auxilliary space.
1 Like
yeah segment tree takes extra memory but I just post it as alternative solution and easy to implement ; P
2 Likes