multiplication and addition range updates using lazy propagation

Правка en2, от whatthemomooofun1729, 2023-09-08 07:52:50

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:

Code

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!

Теги segment tree, lazy propagation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский whatthemomooofun1729 2023-09-08 07:52:50 16
en1 Английский whatthemomooofun1729 2023-09-08 07:52:22 2989 Initial revision (published)