Hi, I'm trying to solve a problem I just gave myself using lazy propagation and segment tree. Essentially, we have some queries on an array, where each query consists of two integers $$$L$$$ and $$$R$$$, and we are supposed to update the array by multiplying each element in the range by $$$2$$$, and then adding $$$1$$$ to every element. Every element a[i] within the range becomes 2 * a[i] + 1. For each query, we just print the sum of all elements.
Let N be the number of elements, A be the array.
So, for this test case:
N = 5. A = {1, 2, 3, 4, 5}. 1 Query: [L, R] = [1, 2]
The answer should be 20, but my code prints 19.
Here is my attempt:
I split up each query into two updates: multiplying everything in the range by 2 and then adding by 1.
It seems that I am propagating correctly, why am I getting the wrong answer? Thank you in advance!
Nevermind, I figured the problem out
Could you share your solution?
Did you stress test your code after this? If you came up with the problem yourself and aren’t using an online judge, it might be wrong on something else, considering the fact that it was wrong for this.
By the way if you create an array b[i] = a[i] + 1 then you can just double each element in b[i] for each operation, then b[i] = a[i] + 1 will still hold so you can sum query then subtract the length of the range to get the answer which means you only need to double in you lazy seg tree