线段树

川长思鸟来 2022-05-17 05:53 316阅读 0赞

**一 概述**

线段树，类似区间树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(logn)。

线段树的每个节点表示一个区间，子节点则分别表示父节点的左右半区间，例如父亲的区间是\[a,b\]，那么(c=(a+b)/2)左儿子的区间是\[a,c\]，右儿子的区间是\[c+1,b\]。

**二 从一个例子理解线段树**

下面我们从一个经典的例子来了解线段树，问题描述如下:从数组arr\[0...n-1\]中查找某个数组某个区间内的最小值，其中数组大小固定，但是数组中的元素的值可以随时更新。

对这个问题一个简单的解法是：遍历数组区间找到最小值，时间复杂度是O(n),额外的空间复杂度O(1)。当数据量特别大，而查询操作很频繁的时候，耗时可能会不满足需求。

另一种解法：使用一个二维数组来保存提前计算好的区间\[i,j\]内的最小值，那么预处理时间为O(n^2)，查询耗时O(1), 但是需要额外的O(n^2)空间，当数据量很大时，这个空间消耗是庞大的，而且当改变了数组中的某一个值时，更新二维数组中的最小值也很麻烦。

我们可以用线段树来解决这个问题：预处理耗时O(n)，查询、更新操作O(logn)，需要额外的空间O(n)。根据这个问题我们构造如下的二叉树

*  叶子节点是原始组数arr中的元素
 *  非叶子节点代表它的所有子孙叶子节点所在区间的最小值

例如对于数组\[2, 5, 1, 4, 9, 3\]可以构造如下的二叉树（背景为白色表示叶子节点，非叶子节点的值是其对应数组区间内的最小值，例如根节点表示数组区间arr\[0...5\]内的最小值是1）： [本文地址][Link 1]

![01204058-426dce8b8a05491b91edeba9ec2e4112.jpg][]

***由于线段树的父节点区间是平均分割到左右子树，因此线段树是完全二叉树***，**对于包含n个叶子节点的完全二叉树，它一定有n-1个非叶节点，总共2n-1个节点**，因此存储线段是需要的空间复杂度是O(n)。那么线段树的操作：创建线段树、查询、节点更新 是如何运作的呢（以下所有代码都是针对求区间最小值问题）？

**2.1 创建线段树**

对于线段树我们可以选择和普通二叉树一样的链式结构。由于线段树是完全二叉树，我们也可以用数组来存储，下面的讨论及代码都是数组来存储线段树，节点结构如下（注意到用数组存储时，有效空间为2n-1,实际空间确不止这么多，比如上面的线段树中叶子节点1、3虽然没有左右子树，但是的确占用了数组空间，实际空间是满二叉树的节点数目： ![2 \* 2 ^\{\\lceil \\log\_2\{n\}  \\rceil\} - 1][2 _ 2 _lceil _log_2_n_ _rceil_ - 1]， ![\\lceil \\log\_2\{n\}  \\rceil][lceil _log_2_n_ _rceil] 是树的高度，但是这个空间复杂度也是O(n)的 ）。

struct SegTreeNode

int val;

\}；

定义包含n个节点的线段树 SegTreeNode segTree\[n\]，segTree\[0\]表示根节点。那么对于节点segTree\[i\]，它的左孩子是segTree\[2\*i+1\],右孩子是segTree\[2\*i+2\]。

[https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2565/pid/3771][https_acm.sdut.edu.cn_onlinejudge2_index.php_Home_Contest_contestproblem_cid_2565_pid_3771]（eg）：

代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef struct node
    {
        long long int data;
    }ST;
    ST tree[400000];//一般开题目要求n的四倍大小
    void creat(int root, int l, int r)
    {
        int mid;
        if(l == r)
        {
            scanf("%lld", &tree[root].data);///不能在拆分的时候，输入数据
            return ;
        }
        mid = (l + r) / 2;
        creat(2*root, l, mid);///将区间不断的拆分， 左边递归调用
        creat(2*root + 1, mid + 1, r);///将区间不断的拆分， 右边递归调用
        tree[root].data = tree[2*root].data + tree[2*root + 1].data;//递归回来求，父亲的区间值
    }
    void updata(int p, long long int v, int l, int r, int root)
    {
        int mid;
        if(l == r)
        {
            tree[root].data += v;
            return ;
        }
        mid = (l + r) / 2;
        if(p <= mid) updata(p, v, l, mid, 2 * root);///判断p是在左边的区间还是右边的区间
        else updata(p, v, mid+1, r, 2 * root + 1);
        tree[root].data = tree[2 * root].data + tree[2 * root + 1].data;///递归回来，更新父亲的区间值
    }
    long long sum(int L, int R, int l, int r, int root)
    {
        int mid;
        long long int red = 0;
        if(L <= l && R >= r) return tree[root].data;///如果区间满足L,R的范围就返回对于的区间值
        mid = (l + r) / 2;
        if(L <= mid) 
            red += sum(L, R, l, mid, 2 * root);///左边求值 同时求和
        if(R > mid) 
        red += sum(L, R, mid + 1, r, 2 * root + 1);///右边求值 同时求和
        return red;///返回结果
    
    }
    int main()
    {
        int n, m, num, p, L, R;
        long long int v;
        while(cin>>n)
        {
            creat(1, 1, n);///从下标1到n构建 线段树 数组， 分别表示 根节点下标，区间左边界，区间右边界
            scanf("%d", &m);///m次操作
            while(m--)
            {
                scanf("%d", &num);
                if(num == 1)///第p个数的值增加v
                {
                    scanf("%d %lld", &p, &v);
                    updata(p, v, 1, n, 1);///更新值，同时调整线段树
                }
                else if(num == 2)///求L,R区间的值
                {
                    scanf("%d %d", &L, &R);
                    printf("%lld\n", sum(L, R, 1, n, 1));///求值
                }
            }
        }
        return 0;
    }

[Link 1]: http://www.cnblogs.com/TenosDoIt/admin/EditPosts.aspx?postid=3453089
[01204058-426dce8b8a05491b91edeba9ec2e4112.jpg]: /images/20220517/aed8abe0b9f04fefb2000b95f7717acb.png
[2 _ 2 _lceil _log_2_n_ _rceil_ - 1]: http://d2o58evtke57tz.cloudfront.net/wp-content/ql-cache/quicklatex.com-5faa912d34391d3c73250f145b106a73_l3.png
[lceil _log_2_n_ _rceil]: http://d2o58evtke57tz.cloudfront.net/wp-content/ql-cache/quicklatex.com-450213a0ead2f203224923ed77bbc1e5_l3.png
[https_acm.sdut.edu.cn_onlinejudge2_index.php_Home_Contest_contestproblem_cid_2565_pid_3771]: https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2565/pid/3771