线段树

                     

贡献者: 有机物

   线段树(Segment tree)是一种二叉树形的数据结构,用以存储区间或线段,并且可以在 $O(\log N)$ 的时间复杂度查询区间最大值、最小值、总和等属性.

   线段树的存储:

   线段树除了最后一层节点外是一棵满二叉树,因此可以用堆的存储方式来存储线段树. 具体来说就是开一个一维数组,根节点的编号为 $1$,编号为 $x$ 的结点的左子节点的编号为 $x \times 2$,右子节点的编号为:$x \times 2 + 1$,父节点的编号为 $\left\lfloor\dfrac{x}{2}\right\rfloor$.

   因此我们可以用一个结构体来存储线段树,线段树除了最后一层结点外是一棵满二叉树,除了最后一层结点外的结点个数为:$N + \dfrac{N}{2} + \dfrac{N}{4} + \cdots + 2 + 1 = 2N - 1$,最后一层的结点个数最坏情况下是 $2N$ 个结点,所以数组大小应不小于 $4N$ 才能保持不越界.

图
图 1:二叉树视角
图
图 2:区间视角

   可以看出,线段树的每个结点都代表一个区间,叶结点的区间长度都为 $1$,对于每个区间结点 $[l, r]$,左子结点为 $[l, mid]$,右子结点为 $[mid + 1, r]$,$mid = \left\lfloor\dfrac{l+r}{2}\right\rfloor$.

   线段树的建树($\text{build}$)操作

   一般来说,线段树每个结点上存储了很多信息,具体存什么信息得根据具体情况判断,这里以存储区间最大值为例,我们用递归来建树,每个叶结点 $[i, i]$ 保存 $a_i$ 的值,每次递归左子节点和右子节点,最后根据子节点的信息更新当前结点的信息,这一操作称为 $\text{pushup}$ 操作.

图
图 3:$\text{build}$

struct Node {
    int l, r, v;  // v 代表区间最大值
}tr[4 * N];

void build(int u, int l, int r) 
{
    tr[u] = {l, r};
    
    if (l == r) // 叶节点
    {
        tr[u] = {l, r, a[l]};  // 也可只写 tr[u].v = a[l];
        return;
    }
    
    int mid = l + r >> 1;
    build(u << 1, l, mid);          // 左子节点[l, mid],编号为:u << 1
    build(u << 1 | 1, mid + 1, r);  // 右子节点[mid + 1, r],编号为:u << 1 | 1
    pushup(u);
}

build(1, 1, n);   // 调用建树,从根节点开始

   线段树的 $\text{pushup}$ 操作:

   线段树可以很容易的把左右两个子结点的信息上传到当前结点,所以在记录每个结点 $i$ 的最大值就可以用左子节点 $\mathtt{i < < 1}$ 的最大值和右子节点 $\mathtt{i < < 1|1}$ 的最大值两者取一个最大值就是当前结点 $i$ 的最大值.

void pushup(int u)
{
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

   线段树的单点修改($\text{modify}$)操作:

   单点修改操作一般是把 $a[x]$ 的值修改成 $v$,我们从根结点开始,递归左右两个子节点,找到 $[x, x]$ 区间,然后从下往上把对应的父节点保存的最大值进行更新.

图
图 4:$\text{modify}$

void modify(int u, int x, int v)    // 把 a[x] 修改为 v
{
    if (tr[u].l == x && tr[u].r == x) tr[u].v = v;  // 叶节点
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;       // mid 为树中区间的 mid
        if (x <= mid) modify(u << 1, x, v);     // x 属于左半区间
        else modify(u << 1 | 1, x, v);          // x 属于右半区间
        pushup(u);  // 记得更新父节点的值
    }
}

   线段树的区间查询($\text{query}$)操作:

   查询操作一般为查询某个区间的某种属性,例如查询区间 $[l. r]$ 内的最大值.我们只需要从根节点开始递归查询,会出现如下几种情况:

  1. 查询的区间 $[l, r]$ 完全包含了当前结点的代表区间,则直接返回该区间的最大值,因为没必要再递归查询下去了.
  2. 查询的区间 $[l, r]$ 与左子节点有交集,则递归查询左子节点
  3. 查询的区间 $[l, r]$ 与右子节点有交集,则递归查询右子节点
图
图 5:$\text{query}$

   查询操作会把询问的区间 $[l, r]$ 分成 $O(\log N)$ 个区间,来简单的证明一下: 在递归每个树上的结点 $[T_l, T_r]$ 时,$mid = \left\lfloor\dfrac{T_l+T_r}{2}\right\rfloor$ 会出现以下几种情况:

  1. $l \leq T_l \leq T_r \leq r$ 即当前树中结点对应的区间完全在查询区间的内部
  2. $T_l \leq l \leq T_r \leq r$ 即只有 $l$ 与当前树中结点对应的区间有交集
    (1) $l > mid$,$l$ 只与当前树中结点对应的区间的右半部分 $[mid + 1, r]$ 有交集;
    (2) $l \leq mid$,$l$ 与当前树中结点对应的区间的左右两边都有交集,需要递归左右两边,但是递归的右子结点会在递归后直接返回,即触发了情况 $1$.
  3. $l \leq T_l \leq r \leq T_r$ 即只有 $r$ 与当前树中结点对应的区间有交集,对应情况 $2$.
  4. $T_l \leq l \leq r \leq T_r$ 即查询区间完全在当前树中结点对应的区间内部.
    (1) $l > mid$ 时只会递归右子结点;
    (2) $r < mid$ 时只会递归左子节点;
    (3) $l$、$r$ 都与当前树中结点对应的区间有交集,此时需要递归左右子结点.
图
图 6:情况 $1$
图
图 7:情况 $2(2)$
图
图 8:情况 $4(3)$

   只有 $4(3)$ 这种情况会对线段树的左右两棵子树递归,但这种操作至多发生一次,也就是最开始递归根结点,然后就变成了前三种情况.

int query(int u, int l, int r)
{
    // 完全包含
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;  
    
    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;
    if (l <= mid) v = query(u << 1, l, r);
    if (r > mid) v = max(v, query(u << 1 | 1, l, r));
    
    return v;
}

   以上就是线段树的基本操作.


致读者: 小时百科一直以来坚持所有内容免费,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 10 元,我们一个星期内就能脱离亏损, 并保证在接下来的一整年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利