Dado un tamaño n en el que inicialmente todos los elementos son 0. La tarea es realizar múltiples consultas de los siguientes dos tipos. Las consultas pueden aparecer en cualquier orden.
1. alternar (inicio, fin): Alternar (0 en 1 o 1 en 0) los valores del rango ‘inicio’ a ‘final’.
2. contar (inicio, final): cuenta el número de 1 dentro del rango dado desde ‘inicio’ hasta ‘final’.
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
Una solución simple para este problema es recorrer el rango completo para la consulta «Alternar» y cuando obtenga la consulta «Contar», cuente todos los 1 para el rango dado. Pero la complejidad del tiempo para este enfoque será O(q*n) donde q=número total de consultas.
Una solución eficiente para este problema es usar Segment Tree con Lazy Propagation . Aquí recopilamos las actualizaciones hasta que recibimos una consulta de «Recuento». Cuando recibimos la consulta de «Recuento», hacemos todas las actualizaciones de Toggle recopiladas previamente en una array y luego contamos el número de 1 dentro del rango dado.
A continuación se muestra la implementación del enfoque anterior:
C++
// 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 itself
// 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
// 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 itself
// 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
Python3
# 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 itself # 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#
// 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 itself
// 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*/
Javascript
<script>
// JavaScript program to implement toggle and
// count queries on a binary array.
let MAX = 100000;
// segment tree to store count
// of 1's within range
let tree=new Array(MAX);
// bool type tree to collect the updates
// for toggling the values of 1 and 0 in
// given range
let lazy = new Array(MAX);
for(let i=0;i<MAX;i++)
{
tree[i]=0;
lazy[i]=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
function toggle(node,st,en,us,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 itself
// 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,
let mid = Math.floor((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
function countQuery(node,st,en,qs,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
let mid = Math.floor((st + en) / 2);
return countQuery((node << 1), st, mid, qs, qe) +
countQuery((node << 1) + 1, mid + 1, en, qs, qe);
}
// Driver Code
let n = 5;
toggle(1, 0, n - 1, 1, 2); // Toggle 1 2
toggle(1, 0, n - 1, 2, 4); // Toggle 2 4
document.write(countQuery(1, 0, n - 1, 2, 3)+"<br>"); // Count 2 3
toggle(1, 0, n - 1, 2, 4); // Toggle 2 4
document.write(countQuery(1, 0, n - 1, 1, 4)+"<br>"); // Count 1 4
// This code is contributed by rag2127
</script>
Producción:
1 2
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA