区间转换为最小前缀,例[3,7]表示为{011,1**}

范围区间进行前缀转换是怎么转换的啊?这个算法一直搞不清
例如:[3,7]表示为{011,100,101,110,111},前缀化后{011,1**}。

[3,7]表示为{011,100,101,110,111},这一步是二进制转换,会吧
然后分类统计下,0开头的和1开头的。前者0+11,后者00 01 10 11都出现了就是1**

自然数写成二进制,然后看成一棵二叉树,类似这样的

        /    \
      /        \
/\        /\

/\ /\ /\ /\
0 1 2 3 4 5 6 7 ....
后面有更多就不写出来了,总之区间有多大,树就有多大
往左为0,往右为1,从根往下走到叶子经过的路径就是这个数的二进制表示
显然,对于[3,7]这个区间,4,5,6,7都在里面,而它们是一棵子树,所以可以前缀化
那么算法就是在这个区间中,找最大的子树,然后就可以提取它们公共前缀,剩下分开来的小区间里面,递归做这件事
在这个例子中就是,找到最大的子树4567,递归找3的最大子树,得到3