Input : n = 5       // we have n = 5 blocks
        toggle 1 2  // change 1 into 0 or 0 into 1
        Toggle 2 4
        Count  2 3  // count all 1's within the range
        Toggle 2 4
        Count  1 4  // count all 1's within the range
Output : Total number of 1's in range 2 to 3 is = 1
         Total number of 1's in range 1 to 4 is = 2

// C++ program to implement toggle and count 
// queries on a binary array. 
#include<bits/stdc++.h> 
using namespace std; 
const int MAX = 100000; 

// segment tree to store count of 1's within range 
int tree[MAX] = {0}; 

// bool type tree to collect the updates for toggling 
// the values of 1 and 0 in given range 
bool lazy[MAX] = {false}; 

// function for collecting updates of toggling 
// node --> index of current node in segment tree 
// st --> starting index of current node 
// en --> ending index of current node 
// us --> starting index of range update query 
// ue --> ending index of range update query 
void toggle(int node, int st, int en, int us, int ue) 
{ 
    // If lazy value is non-zero for current node of segment 
    // tree, then there are some pending updates. So we need 
    // to make sure that the pending updates are done before 
    // making new updates. Because this value may be used by 
    // parent after recursive calls (See last line of this 
    // function) 
    if (lazy[node]) 
    { 
        // Make pending updates using value stored in lazy nodes 
        lazy[node] = false; 
        tree[node] = en - st + 1 - tree[node]; 

        // checking if it is not leaf node because if 
        // it is leaf node then we cannot go further 
        if (st < en) 
        { 
            // We can postpone updating children we don't 
            // need their new values now. 
            // Since we are not yet updating children of 'node', 
            // we need to set lazy flags for the children 
            lazy[node<<1] = !lazy[node<<1]; 
            lazy[1+(node<<1)] = !lazy[1+(node<<1)]; 
        } 
    } 

    // out of range 
    if (st>en || us > en || ue < st) 
        return ; 

    // Current segment is fully in range 
    if (us<=st && en<=ue) 
    { 
        // Add the difference to current node 
        tree[node] = en-st+1 - tree[node]; 

        // same logic for checking leaf node or not 
        if (st < en) 
        { 
            // This is where we store values in lazy nodes, 
            // rather than updating the segment tree itelf 
            // Since we don't need these updated values now 
            // we postpone updates by storing values in lazy[] 
            lazy[node<<1] = !lazy[node<<1]; 
            lazy[1+(node<<1)] = !lazy[1+(node<<1)]; 
        } 
        return; 
    } 

    // If not completely in rang, but overlaps, recur for 
    // children, 
    int mid = (st+en)/2; 
    toggle((node<<1), st, mid, us, ue); 
    toggle((node<<1)+1, mid+1,en, us, ue); 

    // And use the result of children calls to update this node 
    if (st < en) 
        tree[node] = tree[node<<1] + tree[(node<<1)+1]; 
} 

/* node --> Index of current node in the segment tree. 
          Initially 0 is passed as root is always at' 
          index 0 
   st & en  --> Starting and ending indexes of the 
                segment represented by current node, 
                i.e., tree[node] 
   qs & qe  --> Starting and ending indexes of query 
                range */
// function to count number of 1's within given range 
int countQuery(int node, int st, int en, int qs, int qe) 
{ 
    // current node is out of range 
    if (st>en || qs > en || qe < st) 
        return 0; 

    // If lazy flag is set for current node of segment tree, 
    // then there are some pending updates. So we need to 
    // make sure that the pending updates are done before 
    // processing the sub sum query 
    if (lazy[node]) 
    { 
        // Make pending updates to this node. Note that this 
        // node represents sum of elements in arr[st..en] and 
        // all these elements must be increased by lazy[node] 
        lazy[node] = false; 
        tree[node] = en-st+1-tree[node]; 

        // checking if it is not leaf node because if 
        // it is leaf node then we cannot go further 
        if (st<en) 
        { 
            // Since we are not yet updating children os si, 
            // we need to set lazy values for the children 
            lazy[node<<1] = !lazy[node<<1]; 
            lazy[(node<<1)+1] = !lazy[(node<<1)+1]; 
        } 
    } 

    // At this point we are sure that pending lazy updates 
    // are done for current node. So we can return value 
    // If this segment lies in range 
    if (qs<=st && en<=qe) 
        return tree[node]; 

    // If a part of this segment overlaps with the given range 
    int mid = (st+en)/2; 
    return countQuery((node<<1), st, mid, qs, qe) + 
           countQuery((node<<1)+1, mid+1, en, qs, qe); 
} 

// Driver program to run the case 
int main() 
{ 
    int n = 5; 
    toggle(1, 0, n-1, 1, 2);  //  Toggle 1 2 
    toggle(1, 0, n-1, 2, 4);  //  Toggle 2 4 

    cout << countQuery(1, 0, n-1, 2, 3) << endl;  //  Count 2 3 

    toggle(1, 0, n-1, 2, 4);  //  Toggle 2 4 

    cout << countQuery(1, 0, n-1, 1, 4) << endl;  //  Count 1 4 

   return 0; 
} 

// Java program to implement toggle and  
// count queries on a binary array.  

class GFG 
{ 
static final int MAX = 100000; 

// segment tree to store count 
// of 1's within range  
static int tree[] = new int[MAX]; 

// bool type tree to collect the updates  
// for toggling the values of 1 and 0 in 
// given range  
static boolean lazy[] = new boolean[MAX]; 

// function for collecting updates of toggling  
// node --> index of current node in segment tree  
// st --> starting index of current node  
// en --> ending index of current node  
// us --> starting index of range update query  
// ue --> ending index of range update query  
static void toggle(int node, int st,  
                   int en, int us, int ue)  
{ 
    // If lazy value is non-zero for current  
    // node of segment tree, then there are  
    // some pending updates. So we need  
    // to make sure that the pending updates  
    // are done before making new updates. 
    // Because this value may be used by  
    // parent after recursive calls (See last  
    // line of this function)  
    if (lazy[node]) 
    { 

        // Make pending updates using value  
        // stored in lazy nodes  
        lazy[node] = false; 
        tree[node] = en - st + 1 - tree[node]; 

        // checking if it is not leaf node 
        // because if it is leaf node then 
        // we cannot go further  
        if (st < en) 
        { 
            // We can postpone updating children  
            // we don't need their new values now.  
            // Since we are not yet updating children 
            // of 'node', we need to set lazy flags  
            // for the children  
            lazy[node << 1] = !lazy[node << 1]; 
            lazy[1 + (node << 1)] = !lazy[1 + (node << 1)]; 
        } 
    } 

    // out of range  
    if (st > en || us > en || ue < st)  
    { 
        return; 
    } 

    // Current segment is fully in range  
    if (us <= st && en <= ue) 
    { 
        // Add the difference to current node  
        tree[node] = en - st + 1 - tree[node]; 

        // same logic for checking leaf node or not  
        if (st < en) 
        { 
            // This is where we store values in lazy nodes,  
            // rather than updating the segment tree itelf  
            // Since we don't need these updated values now  
            // we postpone updates by storing values in lazy[]  
            lazy[node << 1] = !lazy[node << 1]; 
            lazy[1 + (node << 1)] = !lazy[1 + (node << 1)]; 
        } 
        return; 
    } 

    // If not completely in rang,  
    // but overlaps, recur for children,  
    int mid = (st + en) / 2; 
    toggle((node << 1), st, mid, us, ue); 
    toggle((node << 1) + 1, mid + 1, en, us, ue); 

    // And use the result of children  
    // calls to update this node  
    if (st < en)  
    { 
        tree[node] = tree[node << 1] + 
                     tree[(node << 1) + 1]; 
    } 
} 

/* node --> Index of current node in the segment tree.  
    Initially 0 is passed as root is always at'  
    index 0  
st & en --> Starting and ending indexes of the  
            segment represented by current node,  
            i.e., tree[node]  
qs & qe --> Starting and ending indexes of query  
            range */
// function to count number of 1's  
// within given range  
static int countQuery(int node, int st,  
                      int en, int qs, int qe) 
{ 
    // current node is out of range  
    if (st > en || qs > en || qe < st) 
    { 
        return 0; 
    } 

    // If lazy flag is set for current  
    // node of segment tree, then there  
    // are some pending updates. So we  
    // need to make sure that the pending  
    // updates are done before processing  
    // the sub sum query  
    if (lazy[node]) 
    { 
        // Make pending updates to this node.  
        // Note that this node represents sum  
        // of elements in arr[st..en] and  
        // all these elements must be increased 
        // by lazy[node]  
        lazy[node] = false; 
        tree[node] = en - st + 1 - tree[node]; 

        // checking if it is not leaf node because if  
        // it is leaf node then we cannot go further  
        if (st < en)  
        { 
            // Since we are not yet updating children os si,  
            // we need to set lazy values for the children  
            lazy[node << 1] = !lazy[node << 1]; 
            lazy[(node << 1) + 1] = !lazy[(node << 1) + 1]; 
        } 
    } 

    // At this point we are sure that pending  
    // lazy updates are done for current node.  
    // So we can return value If this segment  
    // lies in range  
    if (qs <= st && en <= qe) 
    { 
        return tree[node]; 
    } 

    // If a part of this segment overlaps 
    // with the given range  
    int mid = (st + en) / 2; 
    return countQuery((node << 1), st, mid, qs, qe) +  
           countQuery((node << 1) + 1, mid + 1, en, qs, qe); 
} 

// Driver Code 
public static void main(String args[]) 
{ 
    int n = 5; 
    toggle(1, 0, n - 1, 1, 2); // Toggle 1 2  
    toggle(1, 0, n - 1, 2, 4); // Toggle 2 4  

    System.out.println(countQuery(1, 0, n - 1, 2, 3)); // Count 2 3  

    toggle(1, 0, n - 1, 2, 4); // Toggle 2 4  

    System.out.println(countQuery(1, 0, n - 1, 1, 4)); // Count 1 4  
} 
} 

// This code is contributed by 29AjayKumar 

# Python program to implement toggle and count 
# queries on a binary array. 
MAX = 100000

# segment tree to store count of 1's within range 
tree = [0] * MAX

# bool type tree to collect the updates for toggling 
# the values of 1 and 0 in given range 
lazy = [False] * MAX

# function for collecting updates of toggling 
# node --> index of current node in segment tree 
# st --> starting index of current node 
# en --> ending index of current node 
# us --> starting index of range update query 
# ue --> ending index of range update query 
def toggle(node: int, st: int, en: int, us: int, ue: int): 

    # If lazy value is non-zero for current node of segment 
    # tree, then there are some pending updates. So we need 
    # to make sure that the pending updates are done before 
    # making new updates. Because this value may be used by 
    # parent after recursive calls (See last line of this 
    # function) 
    if lazy[node]: 

        # Make pending updates using value stored in lazy nodes 
        lazy[node] = False
        tree[node] = en - st + 1 - tree[node] 

        # checking if it is not leaf node because if 
        # it is leaf node then we cannot go further 
        if st < en: 

            # We can postpone updating children we don't 
            # need their new values now. 
            # Since we are not yet updating children of 'node', 
            # we need to set lazy flags for the children 
            lazy[node << 1] = not lazy[node << 1] 
            lazy[1 + (node << 1)] = not lazy[1 + (node << 1)] 

    # out of range 
    if st > en or us > en or ue < st: 
        return

    # Current segment is fully in range 
    if us <= st and en <= ue: 

        # Add the difference to current node 
        tree[node] = en - st + 1 - tree[node] 

        # same logic for checking leaf node or not 
        if st < en: 

            # This is where we store values in lazy nodes, 
            # rather than updating the segment tree itelf 
            # Since we don't need these updated values now 
            # we postpone updates by storing values in lazy[] 
            lazy[node << 1] = not lazy[node << 1] 
            lazy[1 + (node << 1)] = not lazy[1 + (node << 1)] 
        return

    # If not completely in rang, but overlaps, recur for 
    # children, 
    mid = (st + en) // 2
    toggle((node << 1), st, mid, us, ue) 
    toggle((node << 1) + 1, mid + 1, en, us, ue) 

    # And use the result of children calls to update this node 
    if st < en: 
        tree[node] = tree[node << 1] + tree[(node << 1) + 1] 

# node --> Index of current node in the segment tree. 
#         Initially 0 is passed as root is always at' 
#         index 0 
# st & en --> Starting and ending indexes of the 
#             segment represented by current node, 
#             i.e., tree[node] 
# qs & qe --> Starting and ending indexes of query 
#             range 
# function to count number of 1's within given range 
def countQuery(node: int, st: int, en: int, qs: int, qe: int) -> int: 

    # current node is out of range 
    if st > en or qs > en or qe < st: 
        return 0

    # If lazy flag is set for current node of segment tree, 
    # then there are some pending updates. So we need to 
    # make sure that the pending updates are done before 
    # processing the sub sum query 
    if lazy[node]: 

        # Make pending updates to this node. Note that this 
        # node represents sum of elements in arr[st..en] and 
        # all these elements must be increased by lazy[node] 
        lazy[node] = False
        tree[node] = en - st + 1 - tree[node] 

        # checking if it is not leaf node because if 
        # it is leaf node then we cannot go further 
        if st < en: 

            # Since we are not yet updating children os si, 
            # we need to set lazy values for the children 
            lazy[node << 1] = not lazy[node << 1] 
            lazy[(node << 1) + 1] = not lazy[(node << 1) + 1] 

    # At this point we are sure that pending lazy updates 
    # are done for current node. So we can return value 
    # If this segment lies in range 
    if qs <= st and en <= qe: 
        return tree[node] 

    # If a part of this segment overlaps with the given range 
    mid = (st + en) // 2
    return countQuery((node << 1), st, mid, qs, qe) + countQuery( 
        (node << 1) + 1, mid + 1, en, qs, qe) 

# Driver Code 
if __name__ == "__main__": 

    n = 5
    toggle(1, 0, n - 1, 1, 2) # Toggle 1 2 
    toggle(1, 0, n - 1, 2, 4) # Toggle 2 4 

    print(countQuery(1, 0, n - 1, 2, 3)) # count 2 3 

    toggle(1, 0, n - 1, 2, 4) # Toggle 2 4 

    print(countQuery(1, 0, n - 1, 1, 4)) # count 1 4 

# This code is contributed by 
# sanjeev2552 

// C# program to implement toggle and  
// count queries on a binary array. 
using System; 

public class GFG{ 

    static readonly int MAX = 100000;  

    // segment tree to store count  
    // of 1's within range  
    static int []tree = new int[MAX];  

    // bool type tree to collect the updates  
    // for toggling the values of 1 and 0 in  
    // given range  
    static bool []lazy = new bool[MAX];  

    // function for collecting updates of toggling  
    // node --> index of current node in segment tree  
    // st --> starting index of current node  
    // en --> ending index of current node  
    // us --> starting index of range update query  
    // ue --> ending index of range update query  
    static void toggle(int node, int st,  
                    int en, int us, int ue)  
    {  
        // If lazy value is non-zero for current  
        // node of segment tree, then there are  
        // some pending updates. So we need  
        // to make sure that the pending updates  
        // are done before making new updates.  
        // Because this value may be used by  
        // parent after recursive calls (See last  
        // line of this function)  
        if (lazy[node])  
        {  

            // Make pending updates using value  
            // stored in lazy nodes  
            lazy[node] = false;  
            tree[node] = en - st + 1 - tree[node];  

            // checking if it is not leaf node  
            // because if it is leaf node then  
            // we cannot go further  
            if (st < en)  
            {  
                // We can postpone updating children  
                // we don't need their new values now.  
                // Since we are not yet updating children  
                // of 'node', we need to set lazy flags  
                // for the children  
                lazy[node << 1] = !lazy[node << 1];  
                lazy[1 + (node << 1)] = !lazy[1 + (node << 1)];  
            }  
        }  

        // out of range  
        if (st > en || us > en || ue < st)  
        {  
            return;  
        }  

        // Current segment is fully in range  
        if (us <= st && en <= ue)  
        {  
            // Add the difference to current node  
            tree[node] = en - st + 1 - tree[node];  

            // same logic for checking leaf node or not  
            if (st < en)  
            {  
                // This is where we store values in lazy nodes,  
                // rather than updating the segment tree itelf  
                // Since we don't need these updated values now  
                // we postpone updates by storing values in lazy[]  
                lazy[node << 1] = !lazy[node << 1];  
                lazy[1 + (node << 1)] = !lazy[1 + (node << 1)];  
            }  
            return;  
        }  

        // If not completely in rang,  
        // but overlaps, recur for children,  
        int mid = (st + en) / 2;  
        toggle((node << 1), st, mid, us, ue);  
        toggle((node << 1) + 1, mid + 1, en, us, ue);  

        // And use the result of children  
        // calls to update this node  
        if (st < en)  
        {  
            tree[node] = tree[node << 1] +  
                        tree[(node << 1) + 1];  
        }  
    }  

    /* node --> Index of current node in the segment tree.  
        Initially 0 is passed as root is always at'  
        index 0  
    st & en --> Starting and ending indexes of the  
                segment represented by current node,  
                i.e., tree[node]  
    qs & qe --> Starting and ending indexes of query  
                range */
    // function to count number of 1's  
    // within given range  
    static int countQuery(int node, int st,  
                        int en, int qs, int qe)  
    {  
        // current node is out of range  
        if (st > en || qs > en || qe < st)  
        {  
            return 0;  
        }  

        // If lazy flag is set for current  
        // node of segment tree, then there  
        // are some pending updates. So we  
        // need to make sure that the pending  
        // updates are done before processing  
        // the sub sum query  
        if (lazy[node])  
        {  
            // Make pending updates to this node.  
            // Note that this node represents sum  
            // of elements in arr[st..en] and  
            // all these elements must be increased  
            // by lazy[node]  
            lazy[node] = false;  
            tree[node] = en - st + 1 - tree[node];  

            // checking if it is not leaf node because if  
            // it is leaf node then we cannot go further  
            if (st < en)  
            {  
                // Since we are not yet updating children os si,  
                // we need to set lazy values for the children  
                lazy[node << 1] = !lazy[node << 1];  
                lazy[(node << 1) + 1] = !lazy[(node << 1) + 1];  
            }  
        }  

        // At this point we are sure that pending  
        // lazy updates are done for current node.  
        // So we can return value If this segment  
        // lies in range  
        if (qs <= st && en <= qe)  
        {  
            return tree[node];  
        }  

        // If a part of this segment overlaps  
        // with the given range  
        int mid = (st + en) / 2;  
        return countQuery((node << 1), st, mid, qs, qe) +  
            countQuery((node << 1) + 1, mid + 1, en, qs, qe);  
    }  

    // Driver Code  
    public static void Main()  
    {  
        int n = 5;  
        toggle(1, 0, n - 1, 1, 2); // Toggle 1 2  
        toggle(1, 0, n - 1, 2, 4); // Toggle 2 4  

        Console.WriteLine(countQuery(1, 0, n - 1, 2, 3)); // Count 2 3  

        toggle(1, 0, n - 1, 2, 4); // Toggle 2 4  

        Console.WriteLine(countQuery(1, 0, n - 1, 1, 4)); // Count 1 4  
    }  
}  

/*This code is contributed by PrinciRaj1992*/

1
2