## Introduction

Counting set bits in a number is not a very hard task. It can be computed easily using the concept of bit manipulation. Here we will be discussing how to count set bits from a given range of values of an array. Here our main objective is to perform such queries on a given array efficiently.

Letâ€™s go through the problem statement. Then we will see the solution approach.

## Problem statement

You are given an array of integers. You are given some queries of ranges. For each query, you need to find the total count of set bits considering all integers of the given range.

Input

```
arr[ ]={1, 5, 3, 8, 7, 2}
query[ ]={{0, 1}, {3, 3}, {2, 5}}
```

Output

```
for query (0,1) : 3
for query (3,3) : 1
for query (2,5) : 7
```

Explanation

```
arr[ ]={1, 5, 3, 8, 7, 2}
Idx: 0 1 2 3 4 5
1=(1)2
5=(101)2
3=(11)2
8=(1000)2
7=(111)2
2=(10)2
So, for range [0,1] count of set bits= 1+2=3;
for range [3,3] count of set bits = 1;
for range [2,5] count of set bits= 2+1+3+1=7
```

Note: Please try to solve the problem first and then see the solution below.