[数据结构与算法]Segment Tree with Pruning（hdu2021第三场）

Segment Tree with Pruning
链接： link.
题目：


题意：
用$n$,$k$构造线段树，问线段树构造的节点个数。
题解：
最开始想打表找规律，一直没有找到，然后发现这个是有公式的，直接带公式就可以了！直接就可以得到最终答案。
公式推导博客指路：link
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll>mp;
ll n,k,cnt=0;
ll find(ll x )
{
	if(x<=k)return 1;
	if(mp[x])return mp[x];
	if(x%2==1)return mp[x]=find(x/2)+find(x/2+1)+1;
	else return mp[x]=find(x/2)*2+1;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		mp.clear();
		cout<<find(n)<<endl;
	}
}