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

题目描述
给定一段线段树构造代码，按如下方式构造线段树。
定义变量ans，初始ans=0
定义函数build(x,y,z)，意义如下
/////////////////////////
start build
赋值 ans=x
判断若(y=z) 则 end build
定义变量mid
赋值 mid=(y+z)/2 {此处除法为下取整}
运行 build(x2,y,mid)
运行 build(x2+1,mid+1,z)
end build
/////////////////////////
你的任务是，对于T组询问，每个询问给出n，求对于每个n，运行build(1,1,n)后，输出ans。对于每个n，询问相互独立，即ans在上一个询问结束后归零。
输入时T单独给出，每个n会存储在数组a中给出。

方法一：递归思想求解

求解思路
对于本题目的求解，我们采用递归的方法来模拟题目所给的build函数，在每次查询更新ans = 0即可。但是如果完全递归，并不能得到ans值，因此我们构造一个线段树，来返回ans值，根据上述的思路即可得到本题的答案。

图片说明

解题代码

class Solution {
public:
    int myans; // build函数中的ans设为全局变量，可以实时更新
    int myans1; // 记录构建线段树过程出现的最大ans
    void build(int x, int y, int z)
    {   //模拟build函数过程
        myans = x; // 声明变量，来记录求解结果
        myans1 = max(myans, myans1);
        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> myres;
        if(T == 0)
            return myres; // 返回结果
        for(int i = 0; i < T; i++) // 构造线段树来记录ans
        {
            myans = 0; //每次查询更新这两个为0
            myans1 = 0;
            build(1, 1, a[i]);
            myres.push_back(myans1);
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：使用栈结构，引入额外的内存地址空间，因此空间复杂度为 $O(N)$

方法二：优化思想求解

求解思路
对于方法一我们对其进行优化，由于最后使用线段树进行ans的求解，因此我们直接模拟线段树来求解本问题。对于线段树的结点，其值可能为(C,C)或(C+1,C)，因此我们对结点进行讨论，构造出深度尽量大的线段树，然后根据最终构造的线段树得到本题的答案。

图片说明

解题代码

class Solution {
public:
    vector<int> wwork(int T, vector<int>& a) {
        vector<int> myres; // 声明变量，保存结果
        if(T == 0) // 0的情况
            return myres;
        for(int i = 0; i < T; i++)
        {   //共T次查询
            int l, r;
            int myans = 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;
                    myans *= 2;
                }
                else
                {
                    n = l;
                    myans = 2 * myans + 1;
                }
            }
            myres.push_back(myans);
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：构造线段树，因此时间复杂度为 $O(NlogN)$
空间复杂度：没有使用额外的内存地址空间，因此空间复杂度为 $O(1)$