[数据结构与算法]杭电多校3-Segment Tree with Pruning

传送门

题意：

用题目所给的方法构建二叉树，求这颗二叉树的节点数。

思路：

采用记忆化搜索，设$tree[r]$为第r个节点下面含有的节点数，这样在后面遇到r时可以直接调用值。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
map<ll,ll>tree;
ll k;
ll build(ll r)
{
	if(r <= k)return 1;
	if(tree[r])return tree[r];
	if(r%2)return tree[r] = build(r/2)+build(r/2+1)+1;
	else return tree[r] = 2*build((r)/2)+1;
	
}

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		tree.clear();
		ll n;
		cin>>n>>k;
		cout<<build(n)<<endl;
		
	}
}