思路：

题目的主要信息：

  • 按照下列要求,使用build(x,y,z)函数构造线段树：
    start build
 赋值 ans=x
 判断 若(y=z) 则 end build
 定义变量mid
 赋值 mid=(y+z)/2 {此处除法为下取整}
 运行 build(x*2,y,mid)
 运行 build(x*2+1,mid+1,z)
end build
  • 一共T个数字，求每个数字单独构造的ans值，意思是每次构造的时候ans要初始化为0

方法一：递归模拟构造法
具体做法：
用递归的方法模拟上述build函数，每次查询前更新ans=0即可。但是如果完全完成递归，并不能在我们需要的ans值出现，因为我们写的函数build会把后续继续递归完，不能直接返回过程中的ans，我们需要解决这个问题。
可以看到题目的示例解析，这个过程就是一个构造线段树最大编号的问题，因此我们返回的ans每次都是该线段树编号最大值，因此我们可以用另一个全局变量记录最大ans。

class Solution {
public:
    int ans; //build函数中的ans设为全局变量，可以实时更新
    int ans1; //记录构建线段树过程出现的最大ans
    void build(int x, int y, int z){ //模拟build函数过程
        ans = x;
        ans1 = max(ans, ans1);
        if(y == z)
            return;
        int mid = (y + z) / 2;
        build(x * 2, y, mid);
        build(x * 2 + 1, mid + 1, z);
    }
    vector<int> wwork(int T, vector<int>& a) {
        vector<int> res;
        if(T == 0)
            return res;
        for(int i = 0; i < T; i++){
            ans = 0; //每次查询更新这两个为0
            ans1 = 0;
            build(1, 1, a[i]);
            res.push_back(ans1);
        }
        return res;
    }
};

复杂度分析：

  • 时间复杂度：，n为数组中元素的最大值，这是最坏情况。而当n等于每一个元素值时，相当于a数组中所有元素相加
  • 空间复杂度：，递归栈空间，res属于函数必要空间，不属于额外空间

方法二：深度构造模拟法
具体做法：
既然已经知道了是求线段树最大编号的问题，我们可以模拟线段树的构造，但是不是像方法一构造出所有节点，而是往尽可能大的深度去构造。由于线段树节点的两个子节点对应区间的大小只可能是或的关系:如果是，那就随便往一边走，否则往那边走，毕竟区间更大，构建出的深度可能更大。所以每次到一个节点就进行一次模拟构造。
不仅如此，我们通过观察可以发现，只有当时，构建出的线段树层数会大于构建出的，因此我们对此可以作出直接的判断，不用再完全模拟线段树构造。
图片说明
如图所示，左边的线段树我们就不再继续构造了，反正最深处也不在它这一边。

class Solution {
public:
    vector<int> wwork(int T, vector<int>& a) {
        vector<int> res;
        if(T == 0) //0的情况
            return res;
        for(int i = 0; i < T; i++){ //共T次查询
            int l, r;
            int ans = 1; //每次初始化ans
            int n = a[i];
            while(n != 1){
                l = n / 2; //两种情况
                r = n - l;
                if(((l & (-l)) == l) && r > l){ //找最深处，只有l为0 1 2 4 8 ……才行
                    n = r;
                    ans *= 2;
                }else{
                    n = l;
                    ans = 2 * ans + 1;
                }
            }
            res.push_back(ans);
        }
        return res;
    }
};

复杂度分析：

  • 时间复杂度：，最坏情况找到深度为，n为数组中元素的最大值
  • 空间复杂度：，无额外空间