Finding number of zeros in a changing array

Question

The problem is pretty much what the title says. There is an n-element(n<10^5) array, which consists of n zeros. There are q operations (q<2*10^5): Each operation can be one of two below:

1. Add x to all elements on a [l,r] range(x can be also negative)
2. Ask for the number of zeros on a [l,r] range

Note that it is guaranteed that absolute values in the array will never get greater than 10^5

I am asking this question because I was reading a solution to another problem where my question was its subproblem. The author said that it can be solved using segment tree with lazy propagation. I can not figure out how to do that. The brute force solution(O(q*n)) is too slow...

What is the most efficient way to implement answering the query considering the first operation? O(q*long(n)) is what I would be guessing.

Example:

 The array is: 0 0 0 0
-> Add 3 from index 2 to index 3:
    The array is now: 0 0 3 3
-> Ask about number of zeros on [1,2]
    The answer is 1
-> Add -3 from index 3 to index 3
    The array is now: 0 0 3 0
-> Ask about number of zeros on [0,3]
    The answer is 3

Answer 1

Ok, I have solved this task. All we have to do is create a segment tree of minimums with lazy propagation, which also counts number of those minimums. In each node of our segment tree we will store 3 values:

1. Minimum from the segment operated by our node.
2. Number of those minimums on a segment operated by our node.
3. Lazy propagation values(values which tell us what should we pass to our sons when visiting this node next time).

When reading from a segment we will get:

1.Minimum on this segment 
2.How many numbers are equal to the minimum on this segment.

If segment's minimum is 0, then we have to simply return the second value. If our minimum is higher than 0, the answer is 0(no zeros found on this segment, because the lowest number is higher than 0). Since read operation, as well as update operations, is O(log(n)), and we have q operations, the complexity of this algorithm is O(q*log(n)), which is sufficient.

Pseudocode:

min_count[2*MAX_N]
val[2*MAX_N]
lazy[2*MAX_N]

values_from_sons(node)
{
    if(node has no childern) stop the function
    
    val[node]=min(val[2*node],val[2*node+1] //it is a segment tree of minimums

    if(val[2*node]<val[2*node+1]) //minimum from the left son  <  minimum from the right son
    {
        min_count[node]=min_count[2*node]
        stop the function
    }

    if(val[2*node]<val[2*node+1]) //minimum from the left son  >  minimum from the right son
    {
        min_count[node]=min_count[2*node]
        stop the function
    }
    if(val[2*node]==val[2*node+1])
    {
        min_count[node]=min_count[2*node]+min_count[2*node+1]; 
        //we have x minimums in the left son, and y non-intersecting with x minimums on the right, so we can sum them up
    }
}

pass(node)
{
    if(node has no childern) stop the function

    //we are passing values to our children when visiting node,
    // remember that array "lazy" stores values which belong to node's sons

    val[2*node]+=lazy[node];
        lazy[2*node]+=lazy[node];

        val[2*node+1]+=lazy[node];
        lazy[2*node+1]+=lazy[node];

        lazy[node]=0;
}

update(node,left,right,s1,s2,add) 
//node-number of a node, [left,right]-segment operated by this node, [s1,s2]-segment on which we want to add "add" value
{
    pass(node)

    if([left,right] and [s1,s2] have no intersections) stop the function
    
    if([left,right] and [s1,s2] have at least one intersection) /// add "add" value to this node's lazy and val
    {
        val[node]+=add
        lazy[node]+=add
        stop the function
    }

    update(values of the left son)
    update(values of the right son)

    values_from_sons(node) 
    //placing this function here updates this node's values when some of his lower ancestors were changed
}

read(node,left,right,s1,s2) 
//node-number of a node, [left,right]-segment operated by this node, [s1,s2]-segment for which we want an answer
// this function returns 2 values - minimum from a [s1,s2] segment, and number of values equal to this minimum
{
    pass(node)

    if([left,right] and [s1,s2] have no intersections) return {INF,0}; //return neutral value of min operation
    
    if([left,right] and [s1,s2] have at least one intersection) return {val[node],min_count[node]}

    vl=read(values of the left son)
    vr=read(values of the right son)

    if(vl<vr)
    {
        //vl has lower minimums, so the answer for this node will be vl
        return vl
    }
    else if(vl>vr)
    {
        //vr has lower minimums, so the answer for this node will be vr
        return vr
    }
    else
    {
        //left and right son have the same minimum, and non intersecting values. Hence we can add them
        return {vl's minimum, vl's count of minimums + vr's count of minimums};
    }

}

ini()
//builds tree. remember that you have to use it before using any of the functions above
{
    //Hence we don't have to worry about beginning values, all of them are set to 0 at the beginning,
    // we just have to set min_count table properly
    for(each leaf[node that has no sons])
    {
        min_cout[leaf]=1;
    }
    for(x=MAX_N-1, x>0, x--)
    {
        min_count[x]=min_count[2*x]+min_count[2*x+1]
    }
}