Segment tree : Lazy Propagation (range MAX update)

문제

입력 : nums, updates, queries 

nums.size < 10^5 

nums[i]>0

updates.size < 10^5

queries.size < 10

 

ex)

nums : [1,2,3,4,5,6,7,8,9,10]

updates : [[1,3,6],[2,2,1],[1,8,2],[7,8,8],[1,4,9]]

queries : [[1,3],[2,4],[5,8],[2,5],[7,9],[2,6]]

 

updates는 [i,j,value] 쌍으로 되어있으며 nums[i:j+1]까지의 값을 value로 업데이트 한다

queries는 [i,j]쌍으로 되었다

updates로 업데이트가 일어날때마다 queires에 있는 모든 element들의 max(nums[i:j+1])을 구해야한다

 

 

Segment Tree

일반적인 segment tree를 쓰면 시간초과가 일어날 수 있다

왜냐하면, range로 업데이트 해야하기 때문에 극단적으로 [0, nums.size()-1]를 업데이트 하려면 모든 트리를 업데이트 해야한다.

 

>> lazy propagation으로 부모가 업데이트 되었으면 lazy로 자식에게 업데이트 해야한다고만 알리고 더이상 업데이트를 진행하지 않는다. lazy에 있는 값을 업데이트 해야할때만 업데이트한다. 코드를 보면 이해가 쉽다

 

brute force로 업데이트하는 것과 값을 비교할수있게 brute_force_nums를 만들었다

class solution:
    def lazyUpdate(self, lx,rx,x):
        if not self.lazy[x]:
            return
        self.tree[x] = self.lazy[x]
        if lx<rx:
            self.lazy[2*x+1] = self.lazy[x]
            self.lazy[2*x+2] = self.lazy[x]
        self.lazy[x]=0
        
    def update(self, l,r,lx,rx,x,v):
        if l>rx or lx>r:
            return
        self.lazyUpdate(lx,rx,x)
        if l<=lx<=rx<=r:
            self.tree[x] = v
            if lx<rx:
                self.lazy[2*x+1] = v
                self.lazy[2*x+2] = v
            return
        mx = (lx+rx)//2
        self.update(l,r,lx,mx,2*x+1,v)
        self.update(l,r,mx+1,rx,2*x+2,v)
        self.tree[x] = max(self.tree[2*x+1], self.tree[2*x+2])
    
    def query(self, l,r,lx,rx,x):
        if l>rx or lx>r:
            return 0
        self.lazyUpdate(lx,rx,x)
        if l<=lx<=rx<=r:
            return self.tree[x]
        mx = (lx+rx)//2
        return max(self.query(l,r,lx,mx,2*x+1), self.query(l,r,mx+1,rx,2*x+2))
    
    def lazyUpdateExample(self, nums, updates, queries):
        self.tree = [0]*4*len(nums)
        self.lazy = [0]*4*len(nums)
        for i in range(len(nums)):
            self.update(i,i,0,len(nums)-1,0,nums[i])
        
        brute_force_nums = nums[:]
        
        for l,r,v in updates:
            self.update(l,r,0,len(nums)-1,0,v)
            for i in range(l,r+1):
                brute_force_nums[i] = v
            for i,j in queries:
                segment_tree_answer = self.query(i,j,0,len(nums)-1,0)
                brute_force_answer = max(brute_force_nums[i:j+1])
                if segment_tree_answer != brute_force_answer:
                    print("wrong answer")
                    print(brute_force_nums)
                    print(segment_tree_answer, brute_force_answer)
                    

solution().lazyUpdateExample(
    [1,2,3,4,5,6,7,8,9,10]
    ,[[1,3,6],[2,2,1],[1,8,2],[7,8,8],[1,4,9]]
    ,[[1,3],[2,4],[5,8],[2,5],[7,9],[2,6]]
    )

 

 

lazy propagation로 이 부분에서 자식 노드 업데이트를 진행하지 않고 멈추기 때문에 O(logn)의 시간복잡도로 업데이트 할 수 있다

        if l<=lx<=rx<=r:
            self.tree[x] = v
            if lx<rx:
                self.lazy[2*x+1] = v
                self.lazy[2*x+2] = v
            return