 ANDMIN - Editorial

#1

Tester: Misha Chorniy
Editorialist: Pushkar Mishra

Medium

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* = bitwiseAnd(A*, 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* = 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* = 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* = 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* 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.

SAMPLE SOLUTIONS:

#2

Why we can’t use lazy propogation here ?

#3

I tried it do with lazy propogation, but got WA( and I am not able to find the bug). Here’s the link to my code-> https://www.codechef.com/viewsolution/10624668.
I am not able to understand my mistake. Any help is highly appreciated.[NOTE: boolean array “check” is used to check if a node in the lazy segment tree contains any value or not].

#4

@sandeep9 . At an intuitive level as it looks , we cant use lazy propagation ! because the moment you update a range with lazy, you need to update the min value ( i.e our solution for the node) at that very moment . But theres no simple way to do so .

suppose theres a node [L,R] with min value A and while updating the solution of this node , you mark it as lazy and update A with A=A&X . This is the thing which is going wrong . Theres no certainty that new solution will be A&X .

EXAMPLE : let the node [L,R] contain values {1,2,3,8} , solution for this node is 1 . now an update query comes with X=7 over [L,R] , now according to the lazy solution the answer will be 1&7= 1. but actually 8&7 = 0 . so our answer should be 0 but you take it as 1.

hope you are getting it !

#5

@pushkarmishra .
We can keep two values in your structure :

1. sol= min value over the range
2. Bor = BitwiseOR over the range.

Now we can update the tree in the building the tree fashion and neglect a range if X&Bor==Bor . quite similar to the editorial though.

#6

Source limit is being given in almost every problem as 50000 Bytes… What does it mean…??
In this problem… The N could be atmost (10^5)…
so, if we declare an integer array of size 10^5… then (10^5)*2 = 200000 Bytes are required…
but source limit is given as only 50000 Bytes…
What does it mean??