Segment tree with lazy add and set

→ Обратите внимание

До соревнования
Codeforces Round (Div. 2)
6 дней

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	jiangly	3977
2	tourist	3815
3	jqdai0815	3682
4	ksun48	3614
5	orzdevinwang	3526
6	ecnerwala	3514
7	Benq	3483
8	hos.lyric	3381
9	gamegame	3374
10	heuristica	3358

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	170
2	-is-this-fft-	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	157
6	Dominater069	156
7	adamant	154
8	luogu_official	152
8	awoo	152
10	TheScrasse	147

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя ns0

Segment tree with lazy add and set

Автор ns0, история, 5 дней назад, По-английски

Hi, I know that we can make lazy modification and also lazy set (setting each element between [l, r] to x). But I wonder if we can do both, I mean there will be 3 queries and one is for modification, one is for setting and one is for getting sum/min/max. If yes, I wonder if we can do it with iterative way?

segment tree, lazy propagation

ns0
5 дней назад
8

Комментарии (8)

Написать комментарий?

omsincoconut

5 дней назад, # |

+24

Both can be done, just have two lazy. If you push set on add then the add is overwritten. If you push add on set then the set got added to. idk how iterative segtrees work in detail but I think it’s also doable.

→ Ответить

nvvy

5 дней назад, # |

-14

Does Segment Tree have fruits?

→ Ответить

VladiG

3 дня назад, # ^ |

Maybe

→ Ответить

LeoPro

4 дня назад, # |

← Rev. 2 →

+23

omsincoconut is correct; I just want to elaborate on his answer a bit.

One of the cleanest ways to write a segment tree is to create two structures: one for storing data and another for storing modifications. After that, in essence, you just need to be able to perform three operations:

• Unite two units of data (take sum/min/max, as in your case)

• Unite two units of modifications

• Apply a unit of modification to a unit of data.

You can check the implementations in the Atcoder Library or my team's teambook (the last one was written based on the Efficient and easy segment trees).

In the case of sum on segment and add to segment, both units of data and modification are just int's: the first one is the sum over the segment, and the second one is the value that needs to be added to the segment. The operations are defined as follows:

(int left, int right) { return left + right; }, 

(int mod1, int mod2) { return mod1 + mod2; }, 

(int sum, int mod, int length) { return sum + mod * length; }

where length is the length of the current segment in the segment tree.

In the case of two lazy modifications, all you need to do is enhance the structure of a modification. Now it should store two integers: add and set. The operation it performs on the segment should go like this: first, add add to all the values on the segment; then, assign set to all of them, provided set != -1. In this case, the operations go like this (let's assume for simplicity that we calculate the minimum over a segment):

(int left, int right) { return min(left, right); }, 

(auto mod1, auto mod2) { 
    if (mod2.set != -1) return {0, mod2.set}; 
    if (mod1.set != -1) return {0, mod1.set + mod2.add}; 
    return {mod1.add + mod2.add, -1}; 
}, 

(int min, auto mod, int length) { return (mod.set != -1 ? mod.set : min + mod.add); }

→ Ответить

ukwho-1

4 дня назад, # |

Can somebody pls tell me where my code goes wrong i am using a flag variable to distinguish between add and set operation.This is segment tree edu section problem part 4-A it gives wrong answer on test 3.

my code

template<typename Node, typename Update>
struct LazySGT {
    vector<Node> tree;
    vector<bool> lazy;
    vector<Update> updates;
    vector<ll> arr; // type may change
    ll n;
    ll s;
    LazySGT(ll a_len, vector<ll> &a) { // change if type updated
        arr = a;
        n = a_len;
        s = 1;
        while(s < 2 * n){
            s = s << 1;
        }
        tree.resize(s); fill(all(tree), Node());
        lazy.resize(s); fill(all(lazy), false);
        updates.resize(s); fill(all(updates), Update());
        build(0, n - 1, 1);
    }
    void build(ll start, ll end, ll index) { // Never change this
        if (start == end)   {
            tree[index] = Node(arr[start]);
            return;
        }
        ll mid = (start + end) / 2;
        build(start, mid, 2 * index);
        build(mid + 1, end, 2 * index + 1);
        tree[index].merge(tree[2 * index], tree[2 * index + 1]);
    }
    void pushdown(ll index, ll start, ll end){
        if(lazy[index]){
            ll mid = (start + end) / 2;
            apply(2 * index, start, mid, updates[index]);
            apply(2 * index + 1, mid + 1, end, updates[index]);
            updates[index] = Update();
            lazy[index] = 0;
        }
    }
    void apply(ll index, ll start, ll end, Update& u){
        if(start != end){
            lazy[index] = 1;
            updates[index].combine(u, start, end);
        }
        u.apply(tree[index], start, end);
    }
    void update(ll start, ll end, ll index, ll left, ll right, Update& u) {  // Never Change this
        if(start > right || end < left)
            return;
        if(start >= left && end <= right){
            apply(index, start, end, u);
            return;
        }
        pushdown(index, start, end);
        ll mid = (start + end) / 2;
        update(start, mid, 2 * index, left, right, u);
        update(mid + 1, end, 2 * index + 1, left, right, u);
        tree[index].merge(tree[2 * index], tree[2 * index + 1]);
    }
    Node query(ll start, ll end, ll index, ll left, ll right) { // Never change this
        if (start > right || end < left)
            return Node();
        if (start >= left && end <= right){
            pushdown(index, start, end);
            return tree[index];
        }
        pushdown(index, start, end);
        ll mid = (start + end) / 2;
        Node l, r, ans;
        l = query(start, mid, 2 * index, left, right);
        r = query(mid + 1, end, 2 * index + 1, left, right);
        ans.merge(l, r);
        return ans;
    }
    void make_update(ll left, ll right, ll val, bool flag) {  // pass in as many parameters as required
        Update new_update = Update(val, flag); // may change
        update(0, n - 1, 1, left, right, new_update);
    }
    Node make_query(ll left, ll right) {
        return query(0, n - 1, 1, left, right);
    }
};

struct Node1 {
    ll val; // may change
    Node1() { // Identity element
        val = 0;    // may change
    }
    Node1(ll p1) {  // Actual Node
        val = p1; // may change
    }
    void merge(Node1 &l, Node1 &r) { // Merge two child nodes
        val = l.val + r.val;  // may change
    }
};

struct Update1 {
    ll val; // may change
    bool set;
    Update1(){ // Identity update
        val = 0;
        set = false;
    }
    Update1(ll val1,bool flag) { // Actual Update
        val = val1;
        set = flag;
    }
    void apply(Node1 &a, ll start, ll end) { // apply update to given node
        a.val = (set ? val * (end - start + 1) : a.val + val * (end - start + 1)); // may change
    }
    void combine(Update1& new_update, ll start, ll end){
        val = (new_update.set ? new_update.val : val + new_update.val);
        set = new_update.set;
    }
};


void solve(){
    ll n;cin>>n;ll q;cin>>q;
    vector<ll> a(n,0);
    LazySGT<Node1,Update1> seg=LazySGT<Node1,Update1> (n, a);
    while(q--){
        ll typ;cin>>typ;
        if(typ==1){
            ll l,r,v;cin>>l>>r>>v;r--;
            seg.make_update(l,r,v,1);
        }else if(typ==2){
            ll l,r,v;cin>>l>>r>>v;r--;
            seg.make_update(l,r,v,0);
        }else{
            ll l,r;cin>>l>>r;r--;
            cout<<seg.make_query(l,r).val<<endl;
        }
    }
}

→ Ответить

lrvideckis

4 дня назад, # |

not sure if this makes it any easier, but if you can solve this problem https://judge.yosupo.jp/problem/range_affine_range_sum then:

range add is just applying function f(x) = 1*x + amount_to_add

range set is applying function f(x) = 0*x + amount_to_set_to

→ Ответить

Tanishq_CF

4 дня назад, # |

I think the question you are asking is already present on codeforces segment tree edu section.

Assignment, Addition, and Sum

I managed to do it with single lazy array using a flag for determining if update is add or set. Here is my Submission. I am using a generic segment tree template and just making the changes in update1() according to operations.If it is set then we override previous updates else we add value on previous updates.

My Code

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

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define all(x) (x).begin(), (x).end()

typedef long long ll;

// Credits to HealthyUG for the inspiration.
// Lazy Segment Tree with Range Updates and Range Queries
// Supports multiple Segment Trees with just a change in the Node and Update
// Very few changes required everytime

template<typename Node, typename Update>
struct LazySGT {
    vector<Node> tree;
    vector<bool> lazy;
    vector<Update> updates;
    vector<ll> arr; // type may change
    ll n;
    ll s;
    LazySGT(ll a_len, vector<ll> &a) { // change if type updated
        arr = a;
        n = a_len;
        s = 1;
        while(s < 2 * n){
            s = s << 1;
        }
        tree.resize(s); fill(all(tree), Node());
        lazy.resize(s); fill(all(lazy), false);
        updates.resize(s); fill(all(updates), Update());
        build(0, n - 1, 1);
    }
    void build(ll start, ll end, ll index) { // Never change this
        if (start == end)   {
            tree[index] = Node(arr[start]);
            return;
        }
        ll mid = (start + end) / 2;
        build(start, mid, 2 * index);
        build(mid + 1, end, 2 * index + 1);
        tree[index].merge(tree[2 * index], tree[2 * index + 1]);
    }
    void pushdown(ll index, ll start, ll end){
        if(lazy[index]){ 
            ll mid = (start + end) / 2;
            apply(2 * index, start, mid, updates[index]);
            apply(2 * index + 1, mid + 1, end, updates[index]);
            updates[index] = Update();
            lazy[index] = 0;
        }
    }
    void apply(ll index, ll start, ll end, Update& u){
        if(start != end){
            lazy[index] = 1;
            updates[index].combine(u, start, end);
        }
        u.apply(tree[index], start, end);
    }
    void update(ll start, ll end, ll index, ll left, ll right, Update& u) {  // Never Change this
        if(start > right || end < left)
            return;
        if(start >= left && end <= right){
            apply(index, start, end, u);
            return;
        }
        pushdown(index, start, end);
        ll mid = (start + end) / 2;
        update(start, mid, 2 * index, left, right, u);
        update(mid + 1, end, 2 * index + 1, left, right, u);
        tree[index].merge(tree[2 * index], tree[2 * index + 1]);
    }
    Node query(ll start, ll end, ll index, ll left, ll right) {  // Never change this
        if (start > right || end < left)
            return Node();
        if (start >= left && end <= right){
            pushdown(index, start, end);
            return tree[index];
        }
        pushdown(index, start, end);
        ll mid = (start + end) / 2;
        Node l, r, ans;
        l = query(start, mid, 2 * index, left, right);
        r = query(mid + 1, end, 2 * index + 1, left, right);
        ans.merge(l, r);
        return ans;
    }
    void make_update(ll left, ll right, ll val, bool flag) {  // pass in as many parameters as required
        Update new_update = Update(val, flag); // may change
        update(0, n - 1, 1, left, right, new_update);
    }
    Node make_query(ll left, ll right) {
        return query(0, n - 1, 1, left, right);
    }
};

struct Node1 {
    ll val; // may change
    Node1() { // Identity element
        val = 0;    // may change
    }
    Node1(ll p1) {  // Actual Node
        val = p1; // may change
    }
    void merge(Node1 &l, Node1 &r) { // Merge two child nodes
        val = l.val + r.val;  // may change
    }
};

struct Update1 {
    ll val; // may change
    bool set;
    Update1(){ // Identity update
        val = 0;
        set = false;
    }
    Update1(ll val1,bool flag) { // Actual Update
        val = val1;
        set = flag;
    }
    void apply(Node1 &a, ll start, ll end) { // apply update to given node
        a.val = (set ? val * (end - start + 1) : a.val + val * (end - start + 1)); // may change
    }
    void combine(Update1& new_update, ll start, ll end){
        val = (new_update.set ? new_update.val : val + new_update.val);
        set = (new_update.set ? true : set);
    }
};


void solve(){
    ll n;cin>>n;ll q;cin>>q;
    vector<ll> a(n,0);
    LazySGT<Node1,Update1> seg=LazySGT<Node1,Update1> (n, a);
    while(q--){
        ll typ;cin>>typ;
        if(typ==1){
            ll l,r,v;cin>>l>>r>>v;r--;
            seg.make_update(l,r,v,1);
        }else if(typ==2){
            ll l,r,v;cin>>l>>r>>v;r--;
            seg.make_update(l,r,v,0);
        }else{
            ll l,r;cin>>l>>r;r--;
            cout<<seg.make_query(l,r).val<<endl;
        }
    }
}

int main() {
// #ifndef ONLINE_JUDGE
// freopen("Error.txt", "w", stderr);
// #endif
// timeval tp;gettimeofday(&tp, 0);C = (int)tp.tv_usec; // (less than modulo)
// assert((ull)(H(1)*2+1-3) == 0);
fastio();
        ll t=1;
        // cin>>t;
        while(t--){
            solve();
        }

    return 0;    
}

→ Ответить

VladiG

3 дня назад, # |

← Rev. 2 →

Keep one lazy for adding and one lazy for clearing, when you do range set you clear the range and you add a value to it.

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 06.01.2025 20:46:48 (l2).

Десктопная версия, переключиться на мобильную.

При поддержке