Problem Link:
author: Roman Rubanenko
tester/editorialist: Utkarsh Lath
Difficulty:
Medium
Pre-requisites:
segment trees
Problem:
Given a big integer N in binary representation. You have to perform updates on this integer. Each update asks you to flip Lth to Rth digit. After each update you have to answer the following question:
How many integers between 0 and N(bot inclusive) have even number of 1s in their binary representation.
Explanation:
The important observation was that given an N, the answer is N/2 + O(1). This is because if we choose any 0 ≤ i ≤ N, then exactly one out of i and i xor 1 has even number of 1s.
If N is odd then 0 ≤ i ≤ N ⇒ 0 ≤ (i xor 1) ≤ N. So every number number with even number of 1s can be paired with another with odd number of 1s. The answer in this case is (N+1)/2.
ans(N) = (N+1)/2 for odd N
If N is even, then
ans(N) = ans(N-1) + ( 1 if (N has even number of 1s) else 0)
Therefore, we need to maintain the value of N, and the number of 1s in N.
In order to do the operations, while maintaining the above parameters, segment trees come to rescue us. We need to use segment trees with lazy propagation.
Any node of segment tree will store the following information:
struct node {
int **num-bits-spanned**, **num-set-bits**;
// **num-bits-spanned** is number of leaves under the current node.
// **num-set-bits** stores how many of those leaves are '1'
int **sum-of-place-values**, **wtd-sum-of-place-values**;
// if the leaves from i to j are spanned by this node,
// **sum-of-place-values** = 2^i + 2^(i+1) ... 2^j
// **wtd-sum-of-place-values** = d(i) * 2^i + d(i+1) * 2^(i+1) ... d(j) * 2^j
// where d(i) is ith digit from the right.
bool **flip**;
// true iff all children leaves of this node have been flipped odd number of times.
}
A leaf of our segtree represents a single digit.
The parameter num-bits-spanned for a leaf is 1, and num-set-bits is the value of that digit.
The parameter sum-of-place-values for a leaf is 2j-1 if the leaf is jth from from the right, and wtd-sum-of-place-values is d(j) * sum-of-place-values.
If left and right children are given, here is how to construct their parent:
node get-parent(node **l-child**, node **r-child**) // "merge" two nodes
node n;
n.**num-bits-spanned** = l-child.**num-bits-spanned** + r-child.**num-bits-spanned**
n.**num-set-bits** = l-child.**num-set-bits** + r-child.**num-set-bits**
n.**sum-of-place-values** = l-child.**sum-of-place-values** + r-child.**sum-of-place-values**
n.**wtd-sum-of-place-values** = l-child.**wtd-sum-of-place-values** + r-child.**wtd-sum-of-place-values**
n.flip = false
return n
If all children of a node should be flipped, here is how to do it:
void flip-node(node& n) { // update a single subtree
n.**num-set-bits** = n.**num-bits-spanned** - n.**num-set-bits**;
// because all 1s become 0 and 0 become 1
n.**wtd-sum-of-place-values** = n.**sum-of-place-values** - n.**wtd-sum-of-place-values**
n.**flip** ^= 1;
// because all children should be informed of this change sometime in future.
}
Note that in the above procedure, num-set-bits and wtd-sum-of-place-values of the relevant node are updated, but those values for its descendants are not updated. Therefore, the children must be updated, but not just now. This is called lazy propagation. The parameter flip is exactly for this purpose. When going down the tree during an update/query, flip should be propagated down
node& **current-node, left-child, right-child**;
if (**current-node.flip**)
flip-node(**left-child**)
flip-node(**right-child**)
**current-node.flip** = 0
Solutions:
Setter’s solution
Tester’s Solution