线段树建树过程的一点规律

下面是一个很简单的建树代码,建树过程中每次访问到叶子节点就可以直接返回,否则还要向下建树。
按照下面的代码中序遍历,给每个节点编号,看看相邻叶子节点编号相差多少。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100001;
int tot = 0,cur = 0,a[500];
struct Node
{
    int ls,rs;
    int cnt;
}tr[maxn*20];

int build(int L,int R)
{
    int k = ++tot;
    printf("L == %d,R == %d,k == %d\n",L,R,k);
    if(L == R)
    {
        printf("相等\n");
        tr[k].cnt = 0;
        a[++cur] = tot;
        return k;
    }
    int M = (L + R)>>1;
    tr[k].ls = build(L,M);
    tr[k].rs = build(M+1,R);
    return k;
}

int main()
{
    int cnt = 255;
    build(1,cnt);
    a[0] = 0;
    for(int i=1;i<=cur;i++)
    {
        //if((a[i] - a[i-1]) != 1)
         //   if((a[i] - a[i-1]) != 2)
           // if((a[i] - a[i-1]) != 3)
           // if((a[i] - a[i-1]) != 4)
          //  if((a[i] - a[i-1]) != 5)
        printf("%d ",a[i]-a[i-1]);
    }
}

一开始是由于看到下面这样的输出信息,才想到看看相邻叶子节点之间相差多少其它节点。


L == 1,R == 255,k == 1
L == 1,R == 128,k == 2
L == 1,R == 64,k == 3
L == 1,R == 32,k == 4
L == 1,R == 16,k == 5
L == 1,R == 8,k == 6
L == 1,R == 4,k == 7
L == 1,R == 2,k == 8
L == 1,R == 1,k == 9
相等
L == 2,R == 2,k == 10
相等
L == 3,R == 4,k == 11
L == 3,R == 3,k == 12
相等
L == 4,R == 4,k == 13
相等
L == 5,R == 8,k == 14
L == 5,R == 6,k == 15
L == 5,R == 5,k == 16

先把cnt设为127。输出信息如下

8 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 1

好多1啊。偶数位上的数字都是1,于是把1去掉

8 2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 6 2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 7 2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 6 2 3 2 4 2 3 2 5 2 3 2 4 2 3

一开始还以为是2 3和2 4和2 3和 2 5,一直看不出什么规律,但发现2 3 2老是重复出现,不同位置的2 3 2之间隔着一个比3大的数。于是又把所有 2 3 2去掉。

8 4 5 4 6 4 5 4 7 4 5 4 6 4 5 4

一开始又以为是4 5和4 6和4 5和4 7,似乎也没啥规律,但4 5 4又再次重复出现,于是再次去掉

8 6 7 6

找到规律后,6 7 6可以肯定也是这样的模式串。我们试试把cnt改成255。如之前把1~5都去掉

9 6 7 6 8 6 7 6

当cnt变为511,得到下面数列

10 6 7 6 8 6 7 6 9 6 7 6 8 6 7 6

去掉6 7 6。又得

10 8 9 8

当cnt变为1023,数列又变成

11 8 9 8 10 8 9 8

相信大家都看出什么来了。把cnt设为2的奇数次方或2的偶数次方,数列的规律也有所不同。稍微思考一下建树的过程,就能知道为什么会有这样的规律。不过还是好神奇。

不过要是将build函数传入的L和R反过了,即

int build(int R,int L)

把cnt改成15

输出信息如下
7 1 2 1 1 4 1 2 1 1 5 1 2 1 1 4 1 2 1 1 6 1 2 1 1 4 1 2 1 3 1 2 1 5 1 2 1 1 4 1 2 1 1
这样1就不是一直出现再偶数位上了,而是从第二个数字开始,每三个数字为一组,出现每组的第一个数字和第三个数字中。去掉1。
7 2 4 2 5 2 4 2 6 2 4 2 3 2 5 2 4 2
这时2就出现在了偶数位上,去掉2
7 4 5 4 6 4 3 5 4
似乎看不出什么规律了。把cnt改成31.
7 1 4 1 2 1 1 3 1 2 1 4 1 4 1 2 1 1 3 1 2 1 5 1 4 1 2 1 1 3 1 2 1 4 1 4 1 2 1 1 3 1 2 1 6 1 4 1 2 1 1 3 1 2 1 4 1 4 1 2 1 1 3 1 4 1 2 1 1 5 1 4 1 2 1 1 3 1 2 1 4 1 4 1 2 1 1 3 1 2 1
这样1变成了从第7个数字开始,每11个数字一组,出现在每组的奇数位上。去掉1
7 4 2 3 2 4 4 2 3 2 5 4 2 3 2 4 4 2 3 2 6 4 2 3 2 4 4 2 3 4 2 5 4 2 3 2 4 4 2 3 2
又变成了从第二个数字开始,每5个数字一组,4 2 3 2为固定前4个数字。但中间似乎并不遵循这个规律。把这固定前小于4的数字去掉
7 4 4 4 5 4 4 4 6 4 4 4 4 5 4 4 4
貌似没有规律,要是说每三个4算一组,那么中间那四个四怎么解释呢?

我们把传参数那个改回来,再改建子树的过程。
tr[k].ls = build(L,M-1);//原来是L,M;

cnt等于63,去掉1以后
6 2 3 2 4 2 3 2 5 2 3 2 4 2 3 2
再看看原来没有修改建子树区间,也就是用L,M的时候,同样cnt等于63,去掉1
7 2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 6 2 3 2 4 2 3 2 5 2 3 2 4 2 3
欸,前者就是后者的后半部分啊,而且刚好是一半啊。去掉4以下的数字更清楚一些
前者
6 4 5 4
后者
7 4 5 4 6 4 5 4

总之这规律有什么用呢?没啥用,但好玩就行了。

Leave a Reply