multiplication and addition range updates using lazy propagation

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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

int N;
vi t, a, laz1, laz2;
// laz1 stores the aggregate of the multiplications
// laz2 stores the aggregate the additions

void build(int u, int l, int r) {
    if (l == r) {
        t[u] = a[l];
    } else {
        int mid = (l + r)/2;
        build(2 * u, l, mid);
        build(2 * u + 1, mid+1, r);
        t[u] = t[2 * u] + t[2 * u + 1];
    }
}

void addd(int u) { // lazy propagation for additions
    laz2[2 * u] += laz2[u];
    laz2[2 * u + 1] += laz2[u];
    t[2 * u] += laz2[u];
    t[2 * u + 1] += laz2[u];
    laz2[u] = 0;
}

void multiply(int u) { // lazy propagation for multiplication
    laz1[2 * u] *= laz1[u];
    laz1[2 * u + 1] *= laz1[u];
    t[2 * u] *= laz1[u];
    t[2 * u + 1] *= laz1[u];
    laz1[u] = 1;
}

void mult(int u, int tl, int tr, int l, int r, int val) {
    if (l > r) return;
    if (tl == l && tr == r) {
        t[u] *= val;
        laz1[u] *= val;
    } else {
        int mid = (tl + tr)/2;
        multiply(u);
        addd(u);
        mult(2 * u, tl, mid, l, min(mid, r), val);
        mult(2 * u + 1, mid+1, tr, max(mid+1, l), r, val);
        t[u] = t[2 * u] + t[2 * u + 1];
    }
}

void add(int u, int tl, int tr, int l, int r, int val) {
    if (l > r) return;
    if (tl == l && tr == r) {
        t[u] += val;
        laz2[u] += val;
    } else {
        int mid = (tl + tr)/2;
        multiply(u);
        addd(u);
        add(2 * u, tl, mid, l, min(mid, r), val);
        add(2 * u + 1, mid+1, tr, max(mid+1, l), r, val);
        t[u] = t[2 * u] + t[2 * u + 1];
    }
}

int main() { 
    setIO("");
    cin >> N;
    t.rsz(4 * N, 0), a.rsz(N), laz1.rsz(4 * N, 1), laz2.rsz(4 * N, 0);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    build(1, 0, N-1);
    int Q;
    cin >> Q;
    while (Q--) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        mult(1, 0, N-1, l, r, 2);
        add(1, 0, N-1, l, r, 1);
        cout << t[1] << endl;
    }
}

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!

Comments (4)

Write comment?

whatthemomooofun1729

14 months ago, # |

Nevermind, I figured the problem out

→ Reply

_bekhruz

5 weeks ago, # ^ |

Could you share your solution?

avighnakc

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.

AksLolCoding

5 weeks ago, # |

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

whatthemomooofun1729's blog