1.
Introduction
2.
Problem statement
3.
Approaches
4.
Code
5.
Code
6.
FAQs
7.
Key Takeaways
Last Updated: Mar 27, 2024

# Queries to Count Array Elements from a Given Range having a Single Set Bit

Malay Gain
0 upvote

## Introduction

To check if a number is having a single bit or not is not a hard task as we need to only check if the number is a power of 2 or not. This can be easily done using bit manipulation in O(1) time. So, finding the count of array elements from a given range having a single set bit can be done in O(n) time. Here we will be working on a number of such queries.

## Problem statement

There is an array of integers. You are given some queries of format {1,l,r} to count array elements from the given range [l,r] having a single set bit and some queries of format {2,i,val} to update the array element at ith index with val.

``````Input
arr[ ]={ 10, 9, 16, 2, 32 }
Q = { { 1, 0, 3 },{ 2, 2, 20 }, { 1, 1, 4 } }

Output
2
2``````

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

## Approaches

Brute force approach

In this approach for each query of 1st type, we will iterate through the range and will increase the count if the current element is having a single set bit i.e. the power of 2.

For 2nd type query, we will update the element of the given index with the given value.

## Code

Output

Complexity

The above approach takes O(q*n) time in the worst case where q is the number of queries and n is the size of the given array.

Optimized approach using segment tree

For this approach, we will take the help of segment tree to solve this query problem more efficiently.

First, we need to build segment tree st[ ] from the given array. Each node of this segment tree will store the count of elements having a single set bit for a range of arr[], the node representing.

• Define a function buildST( ) with parameters idx,low,high. st[idx] stores the count of elements having single set bit for the range [low,high].

• if there is one element in the segment i.e low=high, the node st[idx] stores 1 if the current number is having a single set bit.

• if there is more than one element in the range, recur for left and right subtrees.
• updating the current node with total count of numbers having single set bit for left and right subtree i.e st[idx]=st[2*idx+1]+st[2*idx+2]

For 1st type of query define a function singleBit( idx, low, high, l, r).

• if the current segment [low,high] denoted by node at idx is part of the given range [l,r], return value of st[idx].
• If the segement [low,high] denoted by node at idx is ouside of the given range [l,r], return 0.
• if the given range overlaps with the segment of the current node, recur for the left and right subtree.

For 2nd type of query to update value at index idx, define update(idx,val,low,high,si).

• If low=high and idx=low, the current node is the leaf node of the segment tree. So, st[si] stores 1 if the current number is having a single set bit.

• Otherwise search for idx . If idx<=mid, traverse to left subtree update(idx,val,low,mid,2*si+1). Else traverse to right subtree by calling update(idx,val,mid+1,high,2*si+2).

## Code

Output

Complexity

The time complexity of the above approach O(n*log n + q*log n) where (nlogn) is time for constructing segment tree and (q*log n) is the time required for q queries.

Space complexity is O(n) as extra space is used for constructing a segment tree.

## FAQs

1. What is a segment tree?
A segment tree is a special kind of data structure that is used to store information about intervals or segments of an array. It can be represented by an array.

2. What kind of problem can be solved efficiently using a segment tree?
A segment tree is used to solve min, max, or sum queries for a given range on an array as well as update queries in O(log n) time where n is the size of the array.

## Key Takeaways

This article covered how to count array elements from a given range having a single set bit. We have seen the brute force approach as well as segment tree implementation.

To know more about the segment tree you can go through the articles of Coding Ninjas Studio library.

Check out this problem - Duplicate Subtree In Binary Tree

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here.

Happy learning!

Live masterclass