线段树的编号问题

昨天写代码的时候碰到了个有趣的小问题，拿来分享和讨论一下。

原问题是这样的，在若干节点组成的集群上需要维护一个分布而可扩展的线段树(想复习线段树的看这里)，叶节点即集群节点，非叶节点用于统计管辖范围中叶子节点的一些数据。线段树的经典用法，不是么。受ZKW线段树的影响，我偏向于把线段树建立成等高树并直接通过节点编号建立函数映射其左右儿子/父节点的编号。当然最直观的方式就是如ZKW线段树一般，用堆的编号方式编号这颗树:

问题在于，这里的线段树需要有可扩展性：由于维护的是节点集群，随时可能有节点加入或离去——离去的节点尚可保留其位置，但节点的加入带来的节点上限N的变化，会带来一定问题：原有树的编号方式被打乱，所有节点需要重新编号。

问题目标

抽出这个问题，其目标在于维护一个线段树的编号方式，从而使每一个叶节点到根节点的路径在增加树规模的过程中不变。

如上图的8号节点(也就是集群节点1)到根节点的路径是(8,4,2,1)，那么无论集群规模怎么扩大，集群节点1到根节点的路径必须是(8,4,2,1,...)(后面的省略号是可能增加的树层数)

解决方案

最开始和少爷 @俞则明 稍微讨论了下，他给了一个糙快猛的方式..直接按某个确定规则模拟从集群大小只有1开始建树，直到建立完成整个集群，在内存中记录下这棵树即可。的确简单粗暴，用内存记录替代了函数计算。考虑到集群规模不会很大，是个很可行的方式。

但难道就没有更优雅一点的算法么？答案是肯定的。开了开脑洞，我想出这么一个数据结构：(我坚信这个编号方式早就被人提出，但由于见识短浅，并没搜索到，也不知道其名字。本文就以该线段树命名了)

该线段树在N=1时只有一个编号为1的叶子节点，当N扩大时，每当现有高度的二叉树已满，则复制一份现有二叉树，将新的最高位全部改为1，并加上只有最高位为1的根节点。如高度为4的该线段树编号概览如下：

不知道各位有没有找出其中的规律，如果没有，看二进制的编号方式应该能很快发现答案:

其中各节点之间关系以及代码如下：

def fromNodeToLeaf(n):
    #从集群编号(0开始)转换至树上编号
    return (n<<1)+1

def fromLeaftoNode(i):
    #从树上编号转化为集群编号
    return i>>1

def parent(i):
    #获得编号为i的树上结点的父节点编号
    layer=i&-i
    return (i^layer)|(layer<<1)

def left(i):
    #获得编号为i的树上结点的左儿子编号
    return i-((i&-i)>>1)

def right(i):
    #获得编号为i的树上结点的右儿子编号
    return i+((i&-i)>>1)

def getRootLable(leafnum):
    #获取规模为leafnum的集群所需该线段树的根节点编号
    leafnum=((leafnum-1)<<1)|1
    while leafnum>0:
        res=leafnum
        leafnum^=leafnum&-leafnum
    return res

该数据结构以应用在正在写的代码里。

再次声明，这个算法肯定已经有了，只是我比较naive不知道而已...不过上文所写全是我自己脑洞出来的，故请勿就此事的原创性撕逼。如果有人能告诉我这个数据结构的名字我将感激不尽。