线段树编号问题题解

在很早之前研究线段树的时候发现，以常规方法构造出的线段树编号可能并不连续。
因此便有了这一题。

结论1：手写若干个线段树可以发现，若给线段树分层，设区间[1,n]代表的点为第1层，下面是第2层第3层以此类推，我们可以发现，第i+1层的编号永远大于第i层的编号。
证明：首先同层的情况下，左边节点编号小于右边的。第i层最大的编号为最右边的节点，编号为1,3,7,15,31...2^i-1，第i+1层编号最小的节点为最左边的节点，编号为2^i,得证。

结论2：而且对于线段树上的节点x[l,r]，它下方的子树的形态，与l和r具体是多少无关，只与r-l+1的大小有关。
证明：显然。

根据上述结论，我们找寻最大x的时候，并不需要把整棵树造出来，只需要知道，每当我们来到一个节点，往哪边走可以走到最大值。因此可以贪心，如果往左的最大深度>往右的最大深度，根据我们以上的结论，就直接往左。否则往右。

问题就变成了，每次判断长度为m的区间构建出的线段树最大深度。

最简单而直观的方法，就是模拟线段树的构造，当然不是构造出所有节点，而是往尽可能大的深度去构造。由于线段树节点的两个子节点对应区间的大小只可能是(c与c)或(c+1与c)的关系，如果是(c与c)，那就随便往一边走，否则往c+1那边走，毕竟区间更大，构建出的深度可能更大。所以每次到一个节点就进行一次模拟构造，每次模拟构造的复杂度为O(logn)，一共做logn次，所以最终复杂度为O(Tlog^2n)

通过观察可以发现，只有当c=2^a时，c+1构建出的线段树层数会大于c构建出的，因此我们对此作出判断即可，就不需要模拟线段树构造了。复杂度变成了O(Tlogn)。

参考代码：

class Solution {
public:
    /**
     * 
     * @param T int整型 
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> wwork(int T, int* a, int aLen) {
        // write code here
        vector<int> xx;
        for (int i=0;i<aLen;i++)
        {
            int n=a[i];
            int rt=1;
            while (n!=1)
            {
                int l=n/2,r=n-l;
                if ((l&(-l))==l&&r>l)
                {
                    rt=rt*2;
                    n=r;
                }else
                {
                    n=l;
                    rt=rt*2+1;
                }
            }
            xx.push_back(rt);
        }
        return xx;
    }
};