Segment Tree Lazy Push Count

Problem

Count how many times a lazy segment tree pushes a non-zero lazy value to its children. nums is the initial array. queries contains ["add", l, r, val] or ["sum", l, r]; whenever a partial-coverage visit descends through a node with a pending lazy value, that value is pushed to both children before recursing. Return the total number of such pushes.

Hint

A push only happens when a node holds lazy work and the next operation needs to look below it.

Test cases

case 1

in: [[1,2,3,4],[["add",0,3,5],["add",1,2,1],["sum",0,3]]]

expected: 3

case 2

in: [[1,2,3,4],[["add",0,3,5],["sum",0,3],["add",1,2,1],["add",0,0,2]]]

expected: 3

case 3

in: [[1,1,1,1,1,1,1,1],[["add",0,7,3],["add",0,3,1],["query",0,7],["add",4,6,2]]]

expected: 3

case 4

in: [[7],[["add",0,0,1],["sum",0,0]]]

expected: 0

Starter codePython

def lazy_push_count(nums, queries):
    # Your code here
    pass

4 test cases · run your code against them in the editor