ieaskacdnklodkofeakyikg's blog

Segment tree with lazy add and set
By ieaskacdnklodkofeakyikg, history, 21 month(s) 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

»
21 month(s) ago, hide # |
 
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
»
21 month(s) ago, hide # |
 
Vote: I like it -14 Vote: I do not like it

Does Segment Tree have fruits?

→ Reply
»
21 month(s) ago, hide # |
← 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
»
21 month(s) ago, hide # |
 
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
»
21 month(s) ago, hide # |
 
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
»
21 month(s) ago, hide # |
 
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
»
21 month(s) ago, hide # |
← 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
»
20 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Thanks for all

→ Reply
»
11 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

As all mentioned before, yes you can

as I use python, I have just made this template:

Here is the GitHub repo for more updated version: https://github.com/Sadasak/Lazy-Propagations-both-Add-and-Set-in-Segment-Tree



set_def = 10**9 + 1 # put a number out of the range
class LazySegTree:
    def __init__(self, arr):
        self.queryid = 0
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.lazy = [[0, 'a'] for _ in range(4 * self.n)]
        self._build(arr, 1, 0, self.n - 1)

    def _merge(self, a, b):
        return a + b  # change to min(a, b) or max(a, b) for other operations

    def _build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self._build(arr, 2 * node, start, mid)
            self._build(arr, 2 * node + 1, mid + 1, end)
            self.tree[node] = self._merge(self.tree[2 * node], self.tree[2 * node + 1])

    def _apply(self, node, start, end, newstate):

        # self.lazy[node] = self.lazy[node]
        if newstate[1] == 's':
            self.lazy[node] = newstate.copy()
            self.tree[node] = self.lazy[node][0] * (end - start + 1) # change to just add if it's min or max

        elif self.lazy[node][1] == 's':
            self.lazy[node][0] += newstate[0]
            self.tree[node] = self.lazy[node][0] * (end - start + 1) # change to just add if it's min or max

        else:
            self.lazy[node][0] += newstate[0]
            self.tree[node] += self.lazy[node][0] * (end - start + 1) # change to just add if it's min or max


    def _push(self, node, start, end):
        newstate = self.lazy[node]
        if (newstate[0] == 0 and newstate[1] == 'a') or (newstate[0] == set_def and newstate[1] == 's') or start == end: return
        mid = (start + end) // 2
        self._apply(node * 2, start, mid, newstate)
        self._apply(node * 2+1, mid+1, end, newstate)
        self.lazy[node] = [0, 'a']


    def range_add(self, start, end, val):
        return self._range_add( 1, 0, self.n - 1, start, end, [val, 'a'])

    def _range_add(self, node, l, r, start, end, val):
        if r < start or end < l:
            return
        if l >= start and r <= end:
            self._apply(node, l, r, val)
            return
        self._push(node, l, r)
        mid = (l + r) // 2
        self._range_add(node*2, l, mid, start, end, val)
        self._range_add(node*2 + 1, mid+1, r, start, end, val)
        self.tree[node] = self.tree[node*2] + self.tree[node*2 + 1] #change to min or max etc...
    

    def range_set(self, start, end, val):
        return self._range_add( 1, 0, self.n - 1, start, end, [val, 's'])

    def _range_set(self, node, l, r, start, end, val):
        if r < start or end < l:
            return
        if l >= start and r <= end:
            self._apply(node, l, r, val)
            return
        self._push(node, l, r)
        mid = (l + r) // 2
        self._range_set(node*2, l, mid, start, end, val)
        self._range_set(node*2 + 1, mid+1, r, start, end, val)
        self.tree[node] = self.tree[node*2] + self.tree[node*2 + 1] #change to min or max etc...
    
    
    def range_query(self, start, end):
        return self._range_query( 1, 0, self.n - 1, start, end)

    def _range_query(self, node, l, r, start, end):
        if end < l or start > r: 
            return 0 # change to ma ba3raf sara7a if min bas not zero akeed
        if start <= l and end >= r:
            return self.tree[node]
        self._push(node, l, r)
        mid = (l+r) // 2
        # ===================== change ta7et to min or max ========================
        return self._range_query(node*2, l, mid, start, end) + self._range_query(node*2 + 1, mid + 1, r, start, end)
→ Reply