# 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 **2 ^{j-1}** if the leaf is

**j**from from the right, and

^{th}**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