题解 | #线段树编号问题#

思路：

题目的主要信息：

• 已知build的询问过程，对于T个n，运行build(1,1,n)后，输出每个n询问过程中最大的ans。
• ans在每一次询问结束后都清零。

方法一：递归

根据题目意思，直接构造一个函数模拟build的询问过程。同时设置两个全局变量ans和max_ans，设为全局变量的原因是，ans在每次查询后都会清零，同时为了减少在执行build函数时，每次都传递ans参数；max_ans由于要记录每次最大的ans值，设为全局变量比较方便。
总共有T个过程需要查询，构建一个循环依次查询，查询结束后清零ans，同时记录下本次查询中最大的ans值。

具体做法：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param T int整型 
     * @param a int整型vector 
     * @return int整型vector
     */
    int ans;
    int max_ans;
    void build(int x,int y,int z)//build计算过程
    {
        ans=x;
        if(ans>max_ans) max_ans=ans;//保留最大的ans值
        if(y==z)
        {
            return;
        }
        int mid;
        mid=(y+z)/2;
        build(x*2,y,mid);
        build(x*2+1,mid+1,z);
    }
    vector<int> wwork(int T, vector<int>& a) {
        // write code here
        vector<int> result;//result用于保存结果
        for(int i=0;i<T;i++)
        {
            ans=0;//根据题目要求，每次询问结束后ans清零
            max_ans=0;//ans清零，max_ans也清零
            build(1,1,a[i]);
            result.push_back(max_ans);//保存询问结束的最大ans值
        }
        return result;
    }
};

复杂度分析：

• 时间复杂度： ，最坏情况下build的时间复杂度为 ,同时有一层遍历。
• 空间复杂度： ，递归栈占用空间。

方法二：优化模拟

事实上，我们并不需要把整棵树造出来，因为每当我们来到一个节点时可以进行判断往哪个方向继续计算下去可以获得最大值，最简单的判断方法是如果左边深度大于右边深度，那我们只需要计算左边部分；否则计算右边部分。
又因为每次进行左右划分是以mid为分割线的，根据长度奇偶的不同，可能划分为左右相同或左边比右边多1的情况，即left==right或left==right+1。如果left==right，两边继续计算下去深度是一样的；否则往left计算。
下面是优化模拟过程：

通过观察可以发现，只有当right为0，1，2，4……时，right的层数会大于left构建的。
具体做法：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param T int整型 
     * @param a int整型vector 
     * @return int整型vector
     */
    bool is2power(int num)
    {
        if(num==1||num==0) return true;
        int i=1;
        while(i<num)
        {
            i*=2;
        }
        if(i==num) return true;
        else return false;
    }
    vector<int> wwork(int T, vector<int>& a) {
        // write code here
        vector<int> result;//用于保存结果
        for(int i=0;i<T;i++)//遍历求解每个n的最大ans值
        {
            int left,right;//left代表左区间大小，right代表右区间大小
            int n=a[i];
            int ans=1;//初始化ans
            while(n!=1)
            {
                left=n/2;//计算左区间大小
                right=n-left;//计算右区间大小
                if(is2power(left)&&right>left)//判断左区间是否可以可以用2^n表示
                {
                    n=right;
                    ans=ans*2;
                }else{
                    n=left;
                    ans=ans*2+1;
                }
            }
            result.push_back(ans);
        }
        return result;
    }
};

复杂度分析：

• 时间复杂度： ，需要遍历一遍，每一遍相当于用二分。
• 空间复杂度： ,只用了常数空间。