Why my "segment tree lazy propagation range sum" is not working?

Правка en1, от tgbaodeeptry, 2021-05-27 18:43:05

Hello guys, after learning Segment Tree, I approach to learn segment tree with LAZY PROPAGATION I tried to implemented it by do this task increase V to all elements in range a to b and get sum of elements in this range. This is my code:

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    int lazy;
};

struct Segment {
    int n;
    Node nodes[400001];

    Segment (int n) {
        this->n = n;

        for (int i = 0; i <= 4*n; i++) 
            nodes[i] = {0, 0};
    }

    void down(int id) {
        int t = nodes[id].lazy;

        nodes[id << 1].val += t;
        nodes[id << 1].lazy += t;
        nodes[id << 1 | 1].val += t;
        nodes[id << 1 | 1].lazy += t;

        nodes[id].lazy = 0;
    }

    void update(int id, int l, int r, int u, int v, int val) {
        if (l > v || r < u) 
            return;

        if (u <= l && r <= v) {
            nodes[id].val += val;
            nodes[id].lazy += val;
            return;
        }

        down(id);
        
        int m = (l + r) >> 1;
        update(id << 1, l, m, u, v, val);
        update(id << 1 | 1, m + 1, r, u, v, val);

        nodes[id].val = nodes[id << 1].val + nodes[id << 1 | 1].val;
    }

    int get(int id, int l, int r, int u, int v) {
        if (l > v || r < u) {
            return 0;
        }

        if (u <= l && r <= v) 
            return nodes[id].val;

        down(id);

        int m = (l + r) >> 1;
        return get(id << 1, l, m, u, v) + get(id << 1 | 1, m + 1, r, u, v);
    }
};

int main() {
    Segment seg(10);
    seg.update(1, 1, 10, 1, 5, 10);

    cout << seg.get(1, 1, 10, 1, 5) << endl;
}

And the answer after running is 10 (but correct answer is 50). Did I implement wrongly?

Thanks so much, guys :D

Теги #segment tree, #lazy propagation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский tgbaodeeptry 2021-05-27 18:43:05 1919 Initial revision (published)