ns0's blog

Segment tree with lazy add and set
By ns0, history, 3 days ago, In English

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?

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
3 days ago, # |
  Vote: I like it +24 Vote: I do not like it

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.

→ Reply
»
3 days ago, # |
  Vote: I like it -14 Vote: I do not like it

Does Segment Tree have fruits?

→ Reply
»
2 days ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

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); }
→ Reply
»
45 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

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
→ Reply
»
37 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
34 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

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
→ Reply
»
27 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply