ZWK线段树

前言一:

建议在阅读这篇博客前,首先会实现普通的递归线段树。

前言二:

此方法非本人所创,为从其他人博客学习而来。普通用途下(如求和、RMQ等),这个方案能够获得比普通线段树更少的时间消耗,但是使用时也有一些细节值得注意(详见正文),经过几次掉入这些细节的坑中后,我决定将它记录下来。

正文:

首先,我们需要回忆一下一般线段树的点更新操作过程:

假设要构建对一个包含8个元素的数组进行更新与求和的线段树,

假设数组元素序号区间范围是[0, 7],并且现在需要更新2号元素,于是,我们按着:

\([0, 7] \rightarrow [0, 3] \rightarrow [1, 3] \rightarrow [1, 2] \rightarrow [2, 2]\)

这样的深入顺序寻找到了目标位置。

类似的,求任意区间的和,比如[2, 5]便是将表示区间为[2, 2], [3, 3], [4, 5]的三个结点存储的值求和,便得到了数组元素[2, 5]的和。

接下来讨论一下如何不使用递归来构建这棵线段树。首先我们需要将区间转化一下,以方便接下来的操作,按照上边的例子,元素序号的区间范围是[0, 7],在序号都是整数的情况下,它等价于[0, 8),如果以[0, 8)作为根节点区间,构建出来的线段树将会如下图,是一棵满二叉树:

这里稍稍做一下说明:在上面这张图中,颜色较深的方格表示的是对应结点在线段树数组中的索引,而颜色较浅的方格则表示的是对应结点代表的区间。

我们可以看到,最后一行的八个结点,就是原始数组中的八个数,他们在线段树中的位置是从8开始到15结束的,这是必然的,对于一棵有n片叶子的满二叉树(备注:这便要求n是2的幂),非叶子结点的个数为\(n – 1\),如果根节点索引是1,则从做到右的第一片叶子的索引一定是n。

由于能够直接找到每个数组元素在线段树中的确切位置,对线段树进行初始化、更新、询问的操作就可以从底部向上进行。

现在总结一下这个算法的核心:如果有n个元素,则i号元素在线段树数组中的索引为\(i + n\)。

下面是三个核心函数的C++代码实现:

// 变量n是data数组中元素的个数
// 数组STree就是线段树数组
void build() {
    // 这第一个循环是将存放在data数组中的原始数据存放到每个对应的叶子上
    for (int i = 0; i < n; i++) {
        STree[n + i] = data[i];
    }
    // 接下来开始从底向上遍历一下所有的结点,进行一次初始化
    for (int i = n - 1; i > 0; i--) {
        STree[i] = STree[i << 1] + STree[i << 1 | 1];
    }
}

void update(int idx, int diff) {
    //idx表示第idx号元素,idx + n就是它在线段树数组中对应叶子的索引值
    STree[idx + n] += diff;
    for (idx += n; idx &gt; 1; idx >>= 1) {
        STree[idx >> 1] = STree[idx] + STree[idx ^ 1];
    // 这里进行与1异或的作用是:在这棵满二叉树中,如果一个结点
    // 是左结点,则它的索引值是一个偶数,则右结点的索引就是将其
    // 索引值二进制表示下最低位换成1;反过来,对于一个右结点,它
    // 需要将二进制表示下的最低位换成0.
    }
}
    // 由于为了构建满二叉树时,我们将这棵线段树的区间修改成了左闭右开区间,所以这里getSum函数获得的是区间[from, to)的和
int getSum(int from, int to) {
    int res = 0;
    for (from += n, to += n; from < to; from >>= 1, to >>= 1) {
    // 对于左边界,如果它是一个右结点,由于其父结点包含了不属于求和
    // 区间的左结点,所以应当抛弃,而直接将当前节点的值加入到函数返回值中
        if (from&1)
            res += STree[from++];
    // 对于右边界,考虑到右边界上的值是不计入求和的,如果它是一个右结点,我们就先将索引值减一,得到左结点,接着将左结点的值加入到返回值中。
        if (to&1)
            res += STree[--to];
    }
    return res;
}

 

最后,来讨论一下最开始提到的细节。如果想要正确使用这棵树,就必须保证构造一棵满二叉树,这样才能够保证数组元素序号与线段树叶子的序号的对应关系成立,这个算法才是正确的。

对于任意个数的数据,假设为size,则应有:

\(n = 2^{log_{2}size}\),

将根节点的区间设置为[0, n),第一片叶子的序号是n,树的大小为2 * n – 1.