线段树简单实现

短命女 2022-05-12 02:30 155阅读 0赞

首先，线段树是一棵满二叉树。（每个节点要么有两个孩子，要么是深度相同的叶子节点）

每个节点维护某个区间，根维护所有的。

![0e2442a7d933c895d47476f7db1373f082020037.jpg][]

如图，区间是二分父的区间。

当有n个元素，初始化需要o(n)时间，对区间操作需要o(logn)时间。

下面给出维护区间最小值的思路和代码

## 功能： ##

## 一样的，依旧是查询和改值。 ##

## 查询\[s,t\]之间最小的数 ##

## 修改某个值 ##

从下往上，每个节点的值为左右区间较小的那一个即可。

这算是简单动态规划思想，做到了o(n)，因为每个节点就访问一遍，而叶子节点一共n个，所以访问2n次即可。

如果利用深搜初始化，会到o(nlogn)。

[https://blog.csdn.net/hebtu666/article/details/81777273][https_blog.csdn.net_hebtu666_article_details_81777273]

有介绍

## 那我们继续说，如何查询。 ##

不要以为它是二分区间就只能查二分的那些区间，它能查任意区间。

比如上图，求1-7的最小值，查询1-4，5-6，7-7即可。

下面说过程：

递归实现：

如果要查询的区间和本节点区间没有重合，返回一个特别大的数即可，不要影响其他结果。

如果要查询的区间完全包含了本节点区间，返回自身的值

都不满足，对左右儿子做递归，返回较小的值。

## 如何更新？ ##

更新ai，就要更新所有包含ai的区间。

可以从下往上不断更新，把节点的值更新为左右孩子较小的即可。

代码实现和相关注释：

注：没有具体的初始化，dp思路写过了，实在不想写了

初始全为INT\_MAX

const int MAX_N=1<<7;
    int n;
    int tree[2*MAX_N-1];
    //初始化
    void gg(int nn)
    {
        n=1;
        while(n<nn)n*=2;//把元素个数变为2的n次方
        for(int i=0;i<2*n-1;i++)tree[i]=INTMAX;//所有值初始化为INTMAX
    }
    
    //查询区间最小值
    int get(int a,int b,int k,int l,int r)//l和r是区间，k是节点下标，求[a,b)最小值
    {
        if(a>=r || b<=l)return INTMAX;//情况1
        if(a<=l || b<=b)return tree[k];//情况2
        int ll=get(a,b,k*2+1,l,(l+r)/2);//以前写过，左孩子公式
        int rr=get(a,b,k*2+2,(l+r)/2,r);//右孩子
        return min(ll,rr);
    }
    
    //更新
    void update(int k,int a)//第k个值更新为a
    {
        //本身
        k+=n-1;//加上前面一堆节点数
        tree[k]=a;
        //开始向上
        while(k>0)
        {
            tree[k]=min(tree[2*k+1],tree[2*k+2]);
            k=(k-1)/2//父的公式，也写过
        }
    }

[0e2442a7d933c895d47476f7db1373f082020037.jpg]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/crop%3D120%2C37%2C1504%2C992%3Bc0%3Dbaike180%2C5%2C5%2C180%2C60/sign=ec67ee96cc5c1038303194828f20a123/0e2442a7d933c895d47476f7db1373f082020037.jpg
[https_blog.csdn.net_hebtu666_article_details_81777273]: https://blog.csdn.net/hebtu666/article/details/81777273