线段树

算法心得

创建时间:2019-09-30 08:37

字数:1.7k 阅读:

评论:

线段树概念
总结

线段树概念

线段树的代码组成：

1：build函数：用于建立整个线段树。

2：upgrade，修改（更新）函数。注意区分：单点更新、区间更新。

3：push_up: 父节点回溯更新函数

如果是区间更新，还需要：push_down，用于：把lazy_tag往下推一级，推到该节点的子节点，并更新该节点左右子节点的：数据值、lazy_tag值。

一、build函数：构建线段树

原理：

开始时是区间[1,n] ,通过递归来逐步分解；

线段树对于每个n的分解是唯一的，所以n相同的线段树，结构相同。

先向下递归地寻找叶节点所在位置（寻找长度为1的区间），

一旦找到就把值放到这个位置，

并向上回溯地修改所有父节点的值。

二、线段树的点修改

首先由根节点1向下递归，找到对应的叶节点，

然后，修改叶节点的值，

再向上返回，在函数返回的过程中，更新路径上的节点的统计信息。

三、线段树的区间修改 —— 引入 lazy_tag

和点修改一样，也是将区间分成子区间，

首先由根节点1向下递归，找到对应的叶节点，

然后，修改本节点的值，

再向上返回，在函数返回的过程中，更新路径上的节点的统计信息。

由此可见向上更新的部分，是一毛一样的。

不同的是，点修改不用向下修改（因为对下面的没有影响，并且也没有下一级节点了，它自己就是最底层叶节点），

可是区间修改，理论上来说是需要向下修改的（因为父区间变动，子区间也会变动）

但是又不能，每次一区间修改，就连带着修改下面的所有子结点，这也tm太慢了。

所以，我们引入了 lazy_tag , 这样就可以不用把区间内的每个点都按照单点更新的方式更新一遍。

我们暂时不更新下面的子节点，而是打上一个标记，什么时候要用到子节点了，什么时候再看着这个标签，更新子节点。

（一般都是sum的时候用push_down更新子节点，因为求和的时候需要先知道两个子节点的值）

lazy_tag的含义：

本节点的统计信息已经根据标记更新过了，但是本节点的子节点仍需要进行更新。（注意：打上懒惰标记的节点，它自己是已经更新过了的）

即，如果要给一个区间的所有值都加上1，那么，实际上并没有给这个区间的所有值都加上1，而是打个标记，记下来，这个节点所包含的区间需要加1.

打上标记后，要根据标记更新本节点的统计信息，比如，如果本节点维护的是区间和，而本节点包含5个数，那么，打上+1的标记之后，要给本节点维护的和+5。

这是向下延迟修改，但是向上显示的信息是修改以后的信息，所以查询的时候可以得到正确的结果。

有的标记之间会相互影响，所以比较简单的做法是，每递归到一个区间，首先下推标记（若本节点有标记，就下推标记），然后再打上新的标记，这样仍然每个区间操作的复杂度是O(log2(n))。

重申，请注意：区间修改才需要懒惰标记，单点修改不需要。

五、push_down函数

一、push_down函数总共需要干三件事：

1：更新左右子节点的lazy值，也就是：把父节点root上面的lazy标记，下推到两个子节点上

2：依据lazy_tag的定义，更新左右子节点的num值，使左右子节点的值成为“被更新过的、正确的值”。

3：把父节点root自身的lazy清空。因为lazy_tag已经被下推，就向上查询来看，父节点自身的lazy_tag已经不需要了

二、注意：

1：开始一切动作之前，要先特判：此父节点上究竟有没有lazy_tag。如果本就没有lazy_tag，千万别更新，会wa。

2：lazy_tag的意义可以被任意定义；关于‘一’中的“更新”，具体的更新方法也是多种多样的，但关键是：

lazy_tag的定义，要能跟 “更新num的操作”对应得上。

也就是说，必须要能够根据lazy_tag，正确更新结点的num值才可以。

数组构建线段树代码

public NumArray(int[] nums) {
    if (nums.length > 0) {
        n = nums.length;
        tree = new int[n * 2];
        buildTree(nums);
    }
}
private void buildTree(int[] nums) {
    for (int i = n, j = 0;  i < 2 * n; i++,  j++)
        tree[i] = nums[j];
    for (int i = n - 1; i > 0; --i)
        tree[i] = tree[i * 2] + tree[i * 2 + 1];
}

更新线段树

当我们更新数组中某个索引 ii 处的元素时，我们需要重建线段树，因为一些树节点上的和值也会随之产生变化。我们将再次使用自下而上的方法。首先更新存储 a[i],a[i] 元素的叶节点。从那里我们将一路向上，直到根节点，并用其子节点值的总和来更新每个父节点的值。

void update(int pos, int val) {
    pos += n;
    tree[pos] = val;
    while (pos > 0) {
        int left = pos;
        int right = pos;
        if (pos % 2 == 0) {
            right = pos + 1;
        } else {
            left = pos - 1;
        }
        // parent is updated after child is updated
        tree[pos / 2] = tree[left] + tree[right];
        pos /= 2;
    }
}

区域和的检索

我们可以通过以下方式使用线段树进行区域和检索 [L, R][L,R]：算法保持循环不变：l \le rl≤r 以及已经算出 [L \ldots l][L…l] 和 [r \ldots R][r…R] 的总和，其中 ll 和 rr 分别是计算总和时的左边界和右边界。每次迭代的范围 [l,r][l,r] 都会缩小，直到在算法的大约 log nlogn 次迭代后两个边界相遇为止。

public int sumRange(int l, int r) {
    // get leaf with value 'l'
    l += n;
    // get leaf with value 'r'
    r += n;
    int sum = 0;
    while (l <= r) {
        if ((l % 2) == 1) {
           sum += tree[l];
           l++;
        }
        if ((r % 2) == 0) {
           sum += tree[r];
           r--;
        }
        l /= 2;
        r /= 2;
    }
    return sum;
}

总结

数组线段树的关键：

1 开2n大的数组

2 满足 n[i] = n[2i] + n[2i+1]，i从1开始

3 在更新操作时要从最底层的节点开始，依次向上更新，直

到更新到跟节点为止

数组线段树的结构真是很巧妙啊

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 583614868@qq.com