线段树专题

左手的ㄟ右手 2022-07-14 01:29 32阅读 0赞

线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段/一段区间（数组中的一段子数组），主要用于解决连续区间的动态查询问题。

**关于线段树的建立（以 1 2 3 4 5为例）**：

![这里写图片描述][20161122204134430]

我们把1~5这5个数，分为2个区间（1，3）和（4，5），之后判断区间是否可以继续再分，（1，3）明显可以分为（1，2）和（3，3）/3 ，把（1，2）继续向下分，3不用继续分，就把a\[3\]存入b数组之中，此时3位于这个数的第3层（设根节点所在的层为第1层），即b\[2\*2+1\]=b\[5\]=a\[3\] ;

同理：  
b\[5\]=a\[3\]; (2\*2+1)  
b\[6\]=a\[4\];  
b\[7\]=a\[5\];  
b\[8\]=a\[1\]; (2\*2\*2)  
b\[9\]=a\[2\];  
b\[1\],b\[2\],b\[3\],b\[4\]为根节点，他们的值为节点中较大的那个值；即  
b\[4\]=max( b\[8\], b\[9\] );  
b\[3\]=max( b\[6\], b\[7\] );  
b\[2\]=max( b\[4\], b\[5\] );  
b\[1\]=max( b\[2\], b\[3\] );  
// 大致的 b\[n\]=max( b\[2^(n+1)+1\] , b\[2^(n+1)+2\] ); (n为2的倍数)

建立线段树的代码（利用二分思想）：

void build(int i,int l,int r) // i:深度   l:左    r：右 
    {
        if(l==r)
            b[i]=a[l];
        else
        {
            build(2*i,l,(l+r)/2);
            build(2*i+1,(l+r)/2+1,r);
            b[i]=max(b[2*i],b[2*i+1]);
        }
    }

--------------------

更新代码(需要把A改成B)： //更新的是节点

1），如果更新的是某个区间，则利用2分的思想，把需要查找的区间分成小的区间，直到不能继续向下进行；  
2），当需要更新的区间是某个节点，即（3，3），只需要更新一个节点  
3），我们进行更新操作的时候，只需要更新b\[i\]位置的数据。  
4），

void updata(int i,int l,int r) // 1 1 n  A--B  1 1 5    // eg: a[]={1 2 3 4 5} ,更新 2 3   
    {
        if(l==r)
            b[i]=B;  b[8]=B;
        else
        {
            int mid=(l+r)/2; 3
            if(A<=mid)
                updata(2*i,l,(l+r)/2);2 1 3 == 4 1 2 == 8 1 1 
               //这里就开始递归调用
            else
                updata(2*i+1,(l+r)/2+1,r);
               //这里就开始递归调用
    
            b[i]=max(b[2*i],b[2*i+1]);
            //在上面的递归过程中，已经更新到b[i]，下面的过程即回溯，更新b[i]相关的节点。
        }
    }

--------------------

1），如果查找的区间超出我们的区间，则返回-1  
2），如果查找的区间在二叉树的某一侧，只需要返回b\[k\]位置的数据  
3），如果查找的区间在二叉树的两侧，我们需要把区间分开查询，较大的数据，为父节点（向下分的时候为一个区间）或者节点（向下无法继续，为一个节点）

查找代码（需要查找的区间为（A,B））： //查找的是区间

int query(int k,int begin,int end)
    {
        int p1,p2;
        if(A>end||B<begin)
            return -1;
        if(begin>=A&&end<=B)
            return b[k];
        p1=query(2*k,begin,(begin+end)/2);
        p2=query(2*k+1,(begin+end)/2+1,end);
        return max(p1,p2);
    }

应用：  
杭电1754：  
[http://acm.hdu.edu.cn/showproblem.php?pid=1754][http_acm.hdu.edu.cn_showproblem.php_pid_1754]

hdu 1754详解：  
[http://blog.csdn.net/acm\_hmj/article/details/53292137][http_blog.csdn.net_acm_hmj_article_details_53292137]

相关解决区间问题的树状数组：  
[http://blog.csdn.net/acm\_hmj/article/category/6528247][http_blog.csdn.net_acm_hmj_article_category_6528247]

[20161122204134430]: /images/20220714/bf5f8e56f68f47288b4a684e096583b0.png
[http_acm.hdu.edu.cn_showproblem.php_pid_1754]: http://acm.hdu.edu.cn/showproblem.php?pid=1754
[http_blog.csdn.net_acm_hmj_article_details_53292137]: http://blog.csdn.net/acm_hmj/article/details/53292137
[http_blog.csdn.net_acm_hmj_article_category_6528247]: http://blog.csdn.net/acm_hmj/article/category/6528247