// c++ code implementation
#include<bits/stdc++.h>
using namespace std;
// constructing segment tree from the given array
void buildST(int idx, int low,int high,vector<int> &st,int arr[])
{
// if there is one element in the array
if(low==high)
{
//the node stores 1 if the number is having single set bit
st[idx]=((arr[low] & (arr[low]1))==0)?1:0;
return;
}
// if there is more than one element,
// recur for left and right subtrees
int mid=(high+low)/2;
buildST(2*idx+1,low,mid,st,arr);
buildST(2*idx+2,mid+1,high,st,arr);
//updating current node with count of numbers having single set bit for [low,high] range
st[idx]=st[2*idx+1]+st[2*idx+2];
}
// function to find count of numbers having single set bit for a given range[l,r]
int singleBit(int idx,int low,int high,int l,int r,vector<int> st)
{
// if the segment of node at idx is part of
// the given range
if(l<=low && r>=high)
{
return st[idx];
}
// the segment of node at idx is ouside of the given range
if(high<l  low>r) return 0;
//if the given range overlaps with the segment of the current node
int mid=(high+low)/2;
int left=singleBit(2*idx+1,low,mid,l,r,st);
int right=singleBit(2*idx+2,mid+1,high,l,r,st);
return (left+right);
}
void update(int idx,int val,int low,int high,int si,vector<int>& st,int arr[])
{
if(low==high)
{
if(low==idx)
{
arr[idx]=val;
//the node stores 1 if the number is having single set bit
st[si]=((arr[idx] & (arr[idx]1))==0)?1:0;
}
return;
}
//mid of the segement [low,high]
int mid=(high+low)/2;
if(idx<=mid)
{
update(idx,val,low,mid,2*si+1,st,arr);
}
else
{
update(idx,val,mid+1,high,2*si+2,st,arr);
}
//updating current node with count of numbers having single set bit for [low,high] range
st[si]=st[2*si+1]+st[2*si+2];
}
// Driver code
int main()
{
int n=5;
int arr[]={10, 9, 16, 2, 32 };
vector<int> st(2*n1); // array representation of segment tree
buildST(0,0,n1,st,arr);
//queries
vector<vector<int>> Q{ { 1, 0, 3 },
{ 2, 2, 20 },
{ 1, 1, 4 } };
for (int i = 0; i < (int)Q.size(); i++)
{
if(Q[i][0]==1)
{
cout<<singleBit(0,0,n1,Q[i][1],Q[i][2],st)<<endl;
}
else
{
update(Q[i][1],Q[i][2],0,n1,0,st,arr);
}
}
}
