Doubt on question:Query Bits

#1

#include
#include
#define ll long long
using namespace std;

ll n;
void buildTree(ll beg,ll end,ll tree,ll idx)
{
if(beg==end)
{
tree[idx]=0;
return;
}
ll mid=(beg+end)/2;
buildTree(beg,mid,tree,2idx);
buildTree(mid+1,end,tree,2*idx+1);

tree[idx]=tree[2*idx]+tree[2*idx+1];

}

ll query(ll *tree,ll beg,ll end,ll l,ll r,ll idx)
{
if(l>end || r<beg)
return 0;

if(l<=beg && r>=end)
{
	return tree[idx];
}
ll mid=(beg+end)/2;
ll left=query(tree,beg,mid,l,r,2*idx);
ll right=query(tree,mid+1,end,l,r,2*idx+1);

return left+right;

}

void update(ll *tree,ll beg,ll end,ll l,ll r,ll idx,ll u)
{
if(l>end || r<beg)
return;

if(beg==end)
{
	if(u==1)
	{
		if(tree[idx]==0)
		tree[idx]=pow(2,n-beg-1);
	}
	else
	{
		if(tree[idx]!=0)
		{
			tree[idx]=0;
		}
	}
	return;
}

ll mid=(beg+end)/2;
update(tree,beg,mid,l,r,2*idx,u);
update(tree,mid+1,end,l,r,2*idx+1,u);

tree[idx]=tree[2*idx]+tree[2*idx+1];

}
int main()
{
ll q;
cin>>n>>q;
ll tree[4*n+1];
buildTree(0,n-1,tree,1);
while(q–)
{
ll g,h,k;
cin>>g>>h>>k;
if(g==0)
{
update(tree,0,n-1,h,k,1,0);
}
else if(g==1)
{
update(tree,0,n-1,h,k,1,1);
}
else
{
cout<<query(tree,0,n-1,h,k,1)<<endl;
}
}
}

it is giving tle
how can i optimise this code

#2

Use lazy propagation since it involves range updates.
Please have a look to my code.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.