multiplication and addition range updates using lazy propagation

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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

15 months ago, # |

Nevermind, I figured the problem out

→ Reply

BehruzbekSuyunov

3 months 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

3 months 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