PROBLEM LINK:
Author: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Pushkar Mishra
DIFFICULTY:
Medium
PREREQUISITES:
Segment Trees
PROBLEM:
Given is an array A of length N. There are two types of operations that we need to handle on this array:
- 0 l r: report the minimum of all the numbers in the range l to r.
- 1 l r x: change all the numbers in the range l to r such that A[i] = bitwiseAnd(A[i], x), \forall l \leq i \leq r.
EXPLANATION:
The nature of the problem clearly hints towards segment trees. We need to efficiently perform the bitwiseAnd operation over a range of numbers and then report the minimum. Reporting the minimum is a standard operation with segment trees: we just have to store the minimum for the corresponding range at each node of the segment tree, and we can answer the queries in \mathcal{O}(\log N) time. But how do we update the minimums when an update operation is requested?
There are no such apparent properties of bitwiseAnd operation that can be applied to a range. There isn’t a notion of an elegant lazy propagation either since we need to perform range-update and range-minimum query.
But there is one nice property that we can observe about our update operation: if in a particular update operation, we have an x such that its i^{th} bit (rightmost bit is 0^{th} bit) is 0, then the i^{th} bit of all the numbers in the range to be updated becomes 0; and for the rest of the execution of our program, remains 0. This is because there is no way to turn a 0 bit to 1 using bitwiseAnd operations only.
This gives us a huge hint about an efficient algorithm that we can use. It tells us that we are only interested in the those bits of x which are 0, because the 1 bits are not going to change anything.
Furthermore, for a particular node in the segment tree, if we know that there exists no number within its range of indexes such that some bit in that number is 1 while the same bit is 0 in x, then we don’t need to bother updating it or its descendants because again nothing is going to change.
So now we know how to build our segment tree, i.e., what information to store in each of its node. Each node of the segment tree will have a boolean array named bits of length 32 and an integer mini. In the array bits, bits[i] = true indicates that there is at least one number in the range represented by the node such that its i^{th} bit is 1. Accordingly, if it is false then there is no number within the range of the node such that its i^{th} bit is 1. The integer mini represents the minimum of all the numbers within the range of the node.
So we now have a way to initialise our segment tree. It is given below as pseudo-code:
void buildNode (node r):
if(r == leaf) {
//let us say that this leaf corresponds to A[index] of the given array.
segTree[r].bits[i] = value of ith bit of A[index]; //for i = 0 to 31
segTree[r].mini = A[index];
return;
}
if(r != leaf) {
buildNode(r->left);
buildNode(r->right);
segTree[r].bits[i] = bitwiseOr of ith bits of r's children; //for i = 0 to 31
segTree[r].mini = minimum(segTree[r->left].mini, segTree[r->right].mini);
}
}
The update function is very similar, except that we impose the condition that we discussed earlier. If a node r falls within the range to be updated, we will recurse down to update its descendents if and only if there exists an i such that the i^{th} bit in x is 0 but segTree[r].bits[i] is 1. If during update, we reach a leaf node, we simply do segTree[leaf].mini = bitwiseAnd(segTree[leaf].mini, x).
The query operation is a standard range-minimum query operation which can be performed with the help of the stored mini values. If the reader doesn’t know about it then he/she can refer here range-min query using segment trees.
What is the complexity of our approach? If we look closely, each bit in each number of the array can only set to 0 once. Reaching a number, i.e., reaching a leaf takes \mathcal{O}(\log N) time in a segment tree. Since there are \log A_{max} bits at maximum in any number within the given array A, therefore, it will take \mathcal{O}(\log A_{max}) per number to set its bits to 0. Since there are N numbers in total, thus, the net complexity is \mathcal{O}(N\log N\log A_{max}) per test case.
Please see editorialist’s/setter’s program for implementation details.
COMPLEXITY:
\mathcal{O}(N\cdot\log N\cdot\log A_{max}) per test case.