multiplication and addition range updates using lazy propagation

#	User	Rating
1	tourist	3757
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

#	User	Contrib.
1	maomao90	171
2	awoo	165
3	adamant	164
4	TheScrasse	159
5	maroonrk	154
6	nor	153
7	-is-this-fft-	152
8	Petr	147
9	orz	146
10	pajenegod	145

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 (2)

Write comment?

whatthemomooofun1729

9 months ago, # |

Nevermind, I figured the problem out

→ Reply

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.

whatthemomooofun1729's blog