LAZY PROPAGATION QUERIES PROBLEM | HARD | MUST DO

https://leetcode.com/problems/handling-sum-queries-after-update/

You are given two 0-indexed arrays nums1 and nums2 and a 2D array queries of queries. There are three types of queries:

For a query of type 1, queries[i] = [1, l, r]. Flip the values from 0 to 1 and from 1 to 0 in nums1 from index l to index r. Both l and r are 0-indexed.
For a query of type 2, queries[i] = [2, p, 0]. For every index 0 <= i < n, set nums2[i] = nums2[i] + nums1[i] * p.
For a query of type 3, queries[i] = [3, 0, 0]. Find the sum of the elements in nums2.
Return an array containing all the answers to the third type queries.



Example 1:

Input: nums1 = [1,0,1], nums2 = [0,0,0], queries = [[1,1,1],[2,1,0],[3,0,0]]
Output: [3]
Explanation: After the first query nums1 becomes [1,1,1]. After the second query, nums2 becomes [1,1,1], so the answer to the third query is 3. Thus, [3] is returned.
Example 2:

Input: nums1 = [1], nums2 = [5], queries = [[2,0,0],[3,0,0]]
Output: [5]
Explanation: After the first query, nums2 remains [5], so the answer to the second query is 5. Thus, [5] is returned.


Constraints:

1 <= nums1.length,nums2.length <= 10^5
nums1.length = nums2.length
1 <= queries.length <= 10^5
queries[i].length = 3
0 <= l <= r <= nums1.length - 1
0 <= p <= 106
0 <= nums1[i] <= 1
0 <= nums2[i] <= 10^9
---------------------------------------------------------------------------------------------------------------------------------------

class Solution {
private:
    vector<long long> tree;
    vector<bool> lazy;
public:
    void build(vector<int> &bits, long long start, long long end, long long parent){
        if(start==end){
            tree[parent]=bits[start];
            return;
        }
        long long mid=(start+end)/2;
        build(bits,start,mid,2*parent+1);
        build(bits,mid+1,end,2*parent+2);
        tree[parent]=tree[2*parent+1]+tree[2*parent+2];
    }

    void querySolver(long long start, long long end, long long qstart, long long qend, long long parent){
        if(start>end){
            return;
        }

        if(lazy[parent]==true){ // lazy happened
            long long totalBits=end-start+1;
            tree[parent]=totalBits-tree[parent];
            if(start!=end){
                lazy[2*parent+1]=!lazy[2*parent+1];
                lazy[2*parent+2]=!lazy[2*parent+2];
            }
            lazy[parent]=false;
        }

        if(qstart>end || qend<start){ // no overlapping
            return;
        }

        if(qstart<=start && qend>=end){  // lazy work
            long long totalBits=end-start+1;
            tree[parent]=totalBits-tree[parent];
            if(start!=end){
                lazy[2*parent+1]=!lazy[2*parent+1];
                lazy[2*parent+2]=!lazy[2*parent+2];
            }
            return;
        }

        long long mid=(start+end)/2;
        querySolver(start,mid,qstart,qend,2*parent+1);
        querySolver(mid+1,end,qstart,qend,2*parent+2);
        tree[parent]=tree[2*parent+1]+tree[2*parent+2];
    }

    vector<long long> handleQuery(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
        /*
        The second query says:-
        nums2[i]=nums2[i]+nums1[i]*p

        Elaborating...
                (nums2[0] + nums1[0]*p) + (nums2[1] + nums1[1]*p) + ........
                Collecting nums2 and nums1 together..
                (nums2[0]+nums2[1]+...) + (nums1[0]+nums1[1]+...) *p
                summation(nums2) + summation(nums1)*p

                So the answer for queries can be given if you can efficiently count the sum of
                nums1 after each update (l,r). nums2 sum is just updated by the new sum.
        */
        long long n=nums1.size();
        lazy.resize(4*n+1);
        tree.resize(4*n+1,false);

        build(nums1,0,n-1,0);

        long long sum_nums2=accumulate(nums2.begin(),nums2.end(),0LL);

        vector<long long> res;

        for(auto query: queries){
            long long type=query[0];
            if(type==1){
                long long l=query[1];
                long long r=query[2];
                querySolver(0,n-1,l,r,0);
            }
            if(type==2){
                long long p=query[1];
                long long newSum=sum_nums2+tree[0]*p;
                sum_nums2=newSum;
            }
            if(type==3){
                res.push_back(sum_nums2);
            }
        }
        return res;
    }

};