Given N coins initially all tails up (let say represented by ‘0’) and a number of queries Q. There are two types of queries. Update: 1) Given indices of a range [L, R]. Flip all the coins between L and R. Get: 2) Given indices of a range [L, R]. Find out the number of coins which are heads up between L and R.
Examples :
Input : N = 4, Q = 5
Get: L = 0, R = 3
Update: L = 1, R = 2
Get: L = 0, R = 1
Update: L = 0, R = 3
Get: L = 0, R = 3
Output : 0
1
2
Explanation :
Query1: A[] = { 0, 0, 0, 0 } Since initially all coins are tails up,
number of heads will be zero
Query2: A[] = { 0, 1, 1, 0 }
Query3: Number of heads up in [0, 1] = 1
Query4: Flip all coins in [0, 3], A[] = { 1, 0, 0, 1 }
Query5: Number of heads up in [0, 3] = 2
Prerequisites: Segment Trees | Lazy Propagation
Method 1(Naive Approach) update(L, R) : Iterate over the subarray from L to R and flip all the coins (i.e. change 0 to 1 and 1 to 0) getHeads(L, R) : To get the number of coins with heads up, simply count the number of ones in range [L, R]. Both update and getHeads function will have O(N) time complexity. The time complexity in worst case is O(Q * N) where Q is number of queries and N is number of coins.
Method 2(Efficient Approach) An efficient method to solve this problem is by using some data structure like Segment Trees which can reduce the time complexity of update and getHeads functions to O(LogN). Build Structure: Each leaf node of segment tree will contain either 0 or 1 depending upon the side of the coin facing up (i.e. if the coin is head up, node will contain 1 otherwise 0). Internal nodes will contain the sum of ones or number of heads of its left child and right child. Thus, the root node will give us the total number of heads in the whole array [0..N-1] Update Structure: Point updates take O(LogN) time but when there are range updates we have to optimize the updates using Lazy Propagation. Below is a modified update method.
UpdateRange(ss, se)
1. If current node's range lies completely in update query range.
...a) Value of current node becomes the difference of total count of coins in the
subtree of current node and current value of node, i.e.
tree[curNode] = (se - ss + 1) - tree[curNode]
...b) Provide the lazy value to its children by setting
lazy[2*curNode] = 1 - lazy[2*curNode]
lazy[2*curNode + 1] = 1 - lazy[2*curNode + 1]
2. If the current node's lazy value is not zero, first update it and provide lazy
value to children.
3. Partial Overlap of current node's range with query range
...a) Recurse for left and right child
...b) Combine the resutls of step (a)
Query Structure: Query Structure will also change a bit in the same way as update structure by checking pending updates and updating them to get the correct query output. Below is the implementation of above approach in C++.
// C program to show segment tree operations like construction, query
// and update
#include <bits/stdc++.h>
using namespace std;
// A utility function to get the middle index from corner indexes.
int getMid(int s, int e) { return s + (e -s)/2; }
/* A recursive function to get the sum of values in given
range of the array. The following are parameters for
this function.
si --> Index of current node in the segment tree.
Initially 0 is passed as root is always at'
index 0
ss & se --> Starting and ending indexes of the
segment represented by current node,
i.e., tree[si]
qs & qe --> Starting and ending indexes of query
range */
int getSumUtil(int *tree, int *lazy, int ss, int se, int qs, int qe, int si)
{
// 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[si] != 0)
{
// Make pending updates to this node. Note that this
// node represents sum of elements in arr[ss..se]
tree[si] = (se - ss + 1) - tree[si];
// checking if it is not leaf node because if
// it is leaf node then we cannot go further
if (ss != se)
{
// Since we are not yet updating children os si,
// we need to set lazy values for the children
lazy[si * 2 + 1] = 1 - lazy[si * 2 + 1];
lazy[si * 2 + 2] = 1 - lazy[si * 2 + 2];
}
// unset the lazy value for current node as it has
// been updated
lazy[si] = 0;
}
// Out of range
if (ss > se || ss > qe || se < qs)
return 0;
// At this point we are sure that pending lazy updates
// are done for current node. So we can return value
// (same as it was for query in our previous post)
// If this segment lies in range
if (ss >= qs && se <= qe)
return tree[si];
// If a part of this segment overlaps with the given
// range
int mid = (ss + se)/2;
return getSumUtil(tree, lazy, ss, mid, qs, qe, 2 * si + 1) +
getSumUtil(tree, lazy, mid + 1, se, qs, qe, 2 * si + 2);
}
// Return sum of elements in range from index qs (quey
// start) to qe (query end). It mainly uses getSumUtil()
int getSum(int *tree, int *lazy, int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n-1 || qs > qe)
{
printf("Invalid Input");
return -1;
}
return getSumUtil(tree, lazy, 0, n-1, qs, qe, 0);
}
/* si -> index of current node in segment tree
ss and se -> Starting and ending indexes of elements for
which current nodes stores sum.
us and ue -> starting and ending indexes of update query */
void updateRangeUtil(int *tree, int *lazy, int si, int ss, int se, 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[si] != 0)
{
// Make pending updates using value stored in lazy
// nodes
tree[si] = (se - ss + 1) - tree[si];
// checking if it is not leaf node because if
// it is leaf node then we cannot go further
if (ss != se)
{
// We can postpone updating children we don't
// need their new values now.
// Since we are not yet updating children of si,
// we need to set lazy flags for the children
lazy[si * 2 + 1] = 1 - lazy[si * 2 + 1];
lazy[si * 2 + 2] = 1 - lazy[si * 2 + 2];
}
// Set the lazy value for current node as 0 as it
// has been updated
lazy[si] = 0;
}
// out of range
if (ss > se || ss > ue || se < us)
return ;
// Current segment is fully in range
if (ss >= us && se <= ue)
{
// Add the difference to current node
tree[si] = (se - ss + 1) - tree[si];
// same logic for checking leaf node or not
if (ss != se)
{
// 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[si * 2 + 1] = 1 - lazy[si * 2 + 1];
lazy[si * 2 + 2] = 1 - lazy[si * 2 + 2];
}
return;
}
// If not completely in rang, but overlaps, recur for
// children,
int mid = (ss + se)/2;
updateRangeUtil(tree, lazy, si * 2 + 1, ss, mid, us, ue);
updateRangeUtil(tree, lazy, si * 2 + 2, mid + 1, se, us, ue);
// And use the result of children calls to update this
// node
tree[si] = tree[si * 2 + 1] + tree[si * 2 + 2];
}
// Function to update a range of values in segment
// tree
/* us and eu -> starting and ending indexes of update query
ue -> ending index of update query
diff -> which we need to add in the range us to ue */
void updateRange(int *tree, int *lazy, int n, int us, int ue)
{
updateRangeUtil(tree, lazy, 0, 0, n-1, us, ue);
}
// A recursive function that constructs Segment Tree for array[ss..se].
// si is index of current node in segment tree st
int constructSTUtil(int arr[], int ss, int se, int *tree, int si)
{
// If there is one element in array, store it in current node of
// segment tree and return
if (ss == se)
{
tree[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements, then recur for left and
// right subtrees and store the sum of values in this node
int mid = getMid(ss, se);
tree[si] = constructSTUtil(arr, ss, mid, tree, si * 2 + 1) +
constructSTUtil(arr, mid+1, se, tree, si * 2 + 2);
return tree[si];
}
/* Function to construct segment tree from given array. This function
allocates memory for segment tree and calls constructSTUtil() to
fill the allocated memory */
int *constructST(int arr[], int n)
{
// Allocate memory for segment tree
//Height of segment tree
int x = (int)(ceil(log2(n)));
//Maximum size of segment tree
int max_size = 2 * (int)pow(2, x) - 1;
// Allocate memory
int *tree = new int[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n-1, tree, 0);
// Return the constructed segment tree
return tree;
}
/* Function to construct lazy array for segment tree. This function
allocates memory for lazy array */
int *constructLazy(int arr[], int n)
{
// Allocate memory for lazy array
//Height of lazy array
int x = (int)(ceil(log2(n)));
//Maximum size of lazy array
int max_size = 2 * (int)pow(2, x) - 1;
// Allocate memory
int *lazy = new int[max_size]();
// Return the lazy array
return lazy;
}
// Driver program to test above functions
int main()
{
// Intialize the array to zero since all coins are tails up
int arr[] = { 0, 0, 0, 0 };
int n = sizeof(arr)/sizeof(arr[0]);
// Build segment tree from given array
int *tree = constructST(arr, n);
// Allocate memory for Lazy array
int *lazy = constructLazy(arr, n);
// Print number of coins which are heads up from index 0 to 3
cout << "Number of Heads in given range = " <<
getSum(tree, lazy, n, 0, 3) << endl;
// UpdateRange: Flip Coins from index 1 to 2
updateRange(tree, lazy, n, 1, 2);
// Print number of coins which are heads up from index 0 to 1
cout << "Number of Heads in given range = " <<
getSum(tree, lazy, n, 0, 1) << endl;
// UpdateRange: Flip Coins from index 0 to 3
updateRange(tree, lazy, n, 0, 3);
// Print number of coins which are heads up from index 0 to 3
cout << "Number of Heads in given range = " <<
getSum(tree, lazy, n, 0, 3) << endl;
return 0;
}
Time Complexity : Each query and each update will take O(LogN) time where N is the number of coins. Hence for Q queries, worst case complexity will be (Q * LogN)
