gpt4 book ai didi

经典区间线段树详解:从原理到实践

转载 作者:撒哈拉 更新时间:2024-12-25 00:47:52 56 4
gpt4 key购买 nike

线段树(Segment Tree)是一种非常高效的树形数据结构,用于解决区间查询和修改问题。本文将通过分步骤讲解,带领读者熟练掌握线段树的原理与实现,并探索其应用场景.

引言:数组区间修改问题

在一些经典问题中,比如给定一个数组,频繁地需要进行以下操作:

  1. 区间查询:查询数组某一子区间内的最大值、最小值、总和等。假定我们总要反复求某个区间内的元素和。
  2. 区间修改:将某个子区间的所有值都进行一次操作,假定我们总要将区间内所有数增加一个固定数值。

暴力方法的困境

对于区间查询,我们可以每次直接遍历子区间计算结果;对于区间修改,可以遍历整个子区间进行更新。然而,区间长度最长可以是几乎整个数组长度,这种方法的时间复杂度为 \(O(n)\),如果操作频繁且数组较大,效率会变得不可接受.

我们需要一种数据结构能够在单次 \(O(\log n)\) 的时间内完成上述操作。线段树应运而生.


线段树的结构与实现

线段树是一种二叉树,用于高效地存储和操作区间信息.

1. 从区间到二叉树

线段树将数组下标空间反复二分划分为多个区间,并使用二叉树存储这些区间的信息:

  • 叶节点:表示数组的单个元素。
  • 内部节点:表示某一子区间的汇总信息(如区间和、最大值等)。

例如,给定数组 [1, 3, 5, 7, 9, 11],其线段树如下:

              [0, 5]
             /       \
        [0, 2]       [3, 5]
       /     \       /     \
   [0, 1]  (2, 2) [3, 4]  (5, 5)
  /    \          /    \
(0, 0)(1, 1)  (3, 3)(4, 4)

小括号为叶节点,即本元素值;中括号即储存区间信息的额外节点,在本题里,他储存区间的总和,这个值由左右儿子计算得出.

2. 空间复杂度与 4 倍数组

普通数组只占用 1 倍空间,不需要多余数据,而线段树的二叉树通常用数组表示。对于大小为 \(n\) 的数组,线段树数组的大小通常是 \(4n\),这是因为:

  1. 线段树是一棵完全二叉树,其节点数不超过 \(2n - 1\)
  2. 而为了保证最快情况下,叶节点的左右空节点也仍无需特殊处理,为了简化代码实现,我们直接分配数组大小为 \(4n\),确保不会越界,形成了惯例。

当然空间复杂度是 \(O(n)\) 的,变化的仅系数。你可以对比上例的数查找.

3. 代码实现

线段树的构建

以下是构建线段树的代码示例:

#include <iostream>
#include <vector>

using namespace std;

vector<int> tree; // 数组保存二叉树
vector<int> lazy; // 二叉树每个节点对应的懒标记,稍后使用
vector<int> arr; // 建树使用的原数据

void build(int node, int start, int end) {
    if (start == end) {
        // 叶节点
        tree[node] = arr[start];
    } else {
        // 非叶节点都被继续二分
        int mid = (start + end) / 2;
        int left_child = 2 * node + 1;
        int right_child = 2 * node + 2;

        build(left_child, start, mid);
        build(right_child, mid + 1, end);

        tree[node] = tree[left_child] + tree[right_child]; // 区间和为左右之和
    }
}

区间查询与修改

1. 区间查询

线段树支持高效的区间查询,通过分治法将问题划分为子区间处理。要求某个区间内所有数的和,只需要将在线段树里不断拆分区间。以下是实现代码:

int query(int node, int start, int end, int l, int r) {
    if (r < start || l > end) {
        return 0; // 完全不相交
    }
    if (l <= start && end <= r) {
        return tree[node]; // 完全包含
    }

    // 部分包含,则交给左右子树处理
    int mid = (start + end) / 2;
    int left_child = 2 * node + 1;
    int right_child = 2 * node + 2;

    int left_sum = query(left_child, start, mid, l, r);
    int right_sum = query(right_child, mid + 1, end, l, r);

    return left_sum + right_sum;
}

假如我们要修改区间 \([1,4]\),可以发现区间最终被拆分到几个子区间,而不一定总是走到最底部,大大提高了效率.

                     [0, 5][36]×
                     /           \
            [0, 2][9]×             [3, 5][27]×
           /           \              /     \
    [0, 1][4]×  (2, 2)[5]√   [3, 4][16]√  (5, 5)[11]
   /       \                 /        \
(0, 0)[1] (1, 1)[3]√      (3, 3)[7] (4, 4)[9]

2. 单点修改

假如要修改数组中的一个元素,那么只要从上往下一路查找到底即可,而底节点改变影响父节点的值,递归结束后重新计算和即可。我们需要更新线段树:

void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        tree[node] = val;
    } else {
        int mid = (start + end) / 2;
        int left_child = 2 * node + 1;
        int right_child = 2 * node + 2;

        if (idx <= mid) {
            update(left_child, start, mid, idx, val);
        } else {
            update(right_child, mid + 1, end, idx, val);
        }

        tree[node] = tree[left_child] + tree[right_child];
    }
}

仍使用刚才的例子,假定修改下标 1 的值:

                     [0, 5][37]×
                     /           \
            [0, 2][10]×             [3, 5][27]
           /           \              /     \
    [0, 1][5]×  (2, 2)[5]   [3, 4][16]   (5, 5)[11]
   /       \                 /        \
(0, 0)[1] (1, 1)[4]√      (3, 3)[7] (4, 4)[9]

3. 区间修改:懒标记

这是线段树最难的一部分。线段树通过懒标记(Lazy Propagation)来优化区间修改。核心思想:延迟更新,将修改操作记录在标记数组中,仅在必要时更新.

具体来说,假如我们要修改某个区间的值(比如都增加 \(a\)),我们仍将其分割到几个子区间,若某区间被完全包含,那么我们就不再向下递归,而是仅对该节点修改,并在该节点处的懒标记设为 \(a\),表明我的所有子节点都应该加上 \(a\),但是尚未实际操作。直到后续某次查询来到这里时,我们才将懒标记清空,并将其向下推一层.

实现代码



void updateRange(int node, int start, int end, int l, int r, int val) {
    if (lazy[node] != 0) { // 来到一个节点,首先检查标记,若存在则下推一层
        tree[node] += (end - start + 1) * lazy[node];
        if (start != end) {
            lazy[2 * node + 1] += lazy[node];
            lazy[2 * node + 2] += lazy[node];
        }
        lazy[node] = 0;
    }

    if (r < start || l > end) { // 完全不相交
        return;
    }

    if (l <= start && end <= r) { // 完全包含,那么在这里停止,并使用懒标记
        tree[node] += (end - start + 1) * val;
        if (start != end) {
            lazy[2 * node + 1] += val;
            lazy[2 * node + 2] += val;
        }
        return;
    }

    // 部分包含,则交给左右子树处理
    int mid = (start + end) / 2;
    updateRange(2 * node + 1, start, mid, l, r, val);
    updateRange(2 * node + 2, mid + 1, end, l, r, val);

    tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}

仍循上例,将\([1,4]\)都增加 1,我们发现在\([3,4]\)处就进行标记,并不再向下传播。由此,区间修改的操作量和区间查询是一致的。若没有懒标记,则每次修改都会推到最底部,这比暴力还劣。所以懒标记是线段树的必须项,而非锦上添花.

虽然其子树的值暂不正确,但是访问子树一定会经过懒标记,当以后任何情况下再次来到这里,都一定会经过懒标记并将其下推,保证了只要你访问了子树。结果总是正确。由此,区间查询函数也需要添加上下推标记段(即if (lazy[node] != 0) 部分).

                     [0, 5][40]×
                     /           \
            [0, 2][11]×             [3, 5][29]×
           /           \              /     \
    [0, 1][5]×  (2, 2)[6]√   [3, 4][18|+1]√  (5, 5)[11]
   /       \                 /        \
(0, 0)[1] (1, 1)[4]√      (3, 3)[7] (4, 4)[9]


为什么线段树分解为 \(O(\log n)\) 段?

我们发现,每次查询或修改时,线段树通过二分方式分解区间,最终把区间分解为 log n 左右个大段,大大提升了效率。这是因为每次递归时都需要访问两个子节点,总共递归深度为 \(\log n\)。即使在最坏情况下,每次递归每层最多访问两个子节点,形成树的左右子树分解,总操作数为树的深度乘以常数项,因此复杂度为 \(O(\log n)\).


拓展知识

指针版线段树

在算法思想完全一样的情况下,二叉树也可以使用指针和动态申请空间来实现,指针版线段树动态分配节点内存,适用于稀疏数组。其可以在更新赋值时再创建节点,内存使用效率高,且不需要 4 倍空间,也叫动态开点线段树。适用于大范围稀疏数据。缺点是编程复杂度较高且常数项性能较低。这种方式本文就不展示了.

在本文章的场景下(维护数组),静态数组版本效率高,更为常用。若要维护巨大但稀疏的值域,则指针版本可节省大量空间.


线段树的其他应用

除了区间查询和修改,线段树还能解决以下问题:

  1. 区间最值:除了区间和,在线段树节点存储区间最小值或最大值。他们的思想几乎一致,仅需要在分支节点中更新和查询时把区间相加改为区间最值即可。
  2. 第 k 小值查询:结合其他算法,可以实现排序和统计信息。
  3. 二维线段树:拓展到二维情况。用于处理平面上的区间问题。

线段树擅长处理可分解的区间性质(如求和、最大值、最小值、乘积等),但对于某些非线性性质,它难以处理或效率低下。,某些区间问题则不能使用线段树,典型的例子是区间众数(Mode)和区间中位数(Median):众数无法通过简单的组合两个子区间的结果来得到,因为它需要全局信息,即子区间的众数不能简单合并为整体区间的众数。中位数也类似,它需要区间内的全局排序信息,不能通过线段树的分治思想直接解决.

最后此篇关于经典区间线段树详解:从原理到实践的文章就讲到这里了,如果你想了解更多关于经典区间线段树详解:从原理到实践的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

56 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com