浅谈线段树兼LuoguP3372 【模板】线段树1 题解

﹏ヽ暗。殇╰゛Y 2021-10-30 05:26 349阅读 0赞

## [原题传送门][Link 1] ##

这道题算得上是最经典的线段树练习题了。

虽然还可以用树状数组、分块等方法完成更为简单，

但是线段树在效率和易理解性上都有一定的优势。

# [线段树][Link 2]的概念性 #

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

对于线段树中的每一个非叶子节点 \[a,b\]\[a,b\] ，它的左儿子表示的区间为 \[a,(a+b)/2\]，右儿子表示的区间为\[(a\+b)/2\+1,b\] 。

因此线段树是平衡二叉树，最后的子节点数目为 N ，即整个线段区间的长度。

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为 O(logN) 。

而未优化的空间复杂度为 2N，因此有时需要离散化让空间压缩。

这是从区间视角看线段 \[1,8\]的线段树结构：

![68817.png][]

黄色的是根节点，绿色的是叶节点。

观察线段树的叶节点，我们可以发现叶节点区间的左端点与右端点相等，这也是为什么它没有左孩子和右孩子的原因。

# 线段树的基本操作 #

## 1. 建树 ##

Q :一个线段树的节点又哪些元素呢？

A :基本的应该有左端点、右端点、节点的值。

而线段树节点的值同分块中每一块的值是一样的，都需要根据题目的需求而改变。

Q :那整体的线段树由什么形式构建呢？

A :线段树的结构是二叉树，所以可以从根节点开始构建，递归它的左右子节点，

直到当前节点是叶子节点（即左端点等于右端点时）就不再继续往下构建。

返回的时候带有节点的值，这些值返回给父节点，父节点的值就由它的左端点（即当前节点）和右端点得到。

而祖父节点的值由它的左节点（即父节点）和右节点得到……

建立线段树的同时回溯即可求出每一个节点的值并构建线段树的左右节点结构。

接下来看代码：

1 void bulid(int t,int l,int r)
     2 {
     3     tree[t].l=l;tree[t].r=r;    //给左节点和有节点赋值
     4     if(l==r)    //如果是叶子节点就不再递归
     5     {
     6         tree[t].val=a[l];
     7         return;
     8     }
     9     int mid=l+r>>1;
    10     bulid(t*2,l,mid);//递归左节点
    11     bulid(t*2+1,mid+1,r);//递归右节点
    12     tree[t].val=tree[t*2].val+tree[t*2+1].val;//回溯之后求值
    13 }

## 2. 区间修改值 ##

先来看一个例子：

修改\[2,6\]的值：

![68832.png][]

分析：

我们要想修改\[2,6\]的值

就得先找到区间\[2,6\]；

因为[2,6]在线段树中不一定是一个整区间，即可能涵盖几个区  间，又可能涵盖不是整个区间的子区间，
    
        所以我们要想找到区间[2,6]就要找到哪些区间包括了[2,6]的子区间；
        {
            我们要想找到哪些区间涵盖了[2,6]的子区间就要遍历整个线段树；
            {
    
                我们要遍历整个线段树就得从根节点开始往左右递归；
                {
                我们要递归就要找到终止的条件——当当前区间和要查找的区间[2,6]完全没有交集的时候就不必再往下递归。
                }
    
            }
    
        }
    }
    再修改区间[2,6]的值
    {
        [2,6]所覆盖的部分由两种情况组成：
        {
            1.不完整的区间
            {
                暴力修改区间里面每一个数的值；
            }
            2.完整的区间
            {
                这里就是线段树效率快的精髓：
    
                我们不一定要继续往下递归修改子区间的值，因为即使修改了子区间的值，也不一定会用到；
    
                同分块的整体标记一样，那么我们就只修改区间的值，我们添加一个元素add（延迟标记)初始值为0.
    
                add是延迟标记，表示当前节点的子节点还没有更新，
    
    　　　　　　add在要把整个区间修改的时候用到。使用时我们不修改子区间的值，只在当前区间的add加上应该加的值。
    
    　　　　　　也就是说，add的作用是以修改它的值来简化修改每一个子区间的值，先把这个事情延迟不做，因为并不是必要的。
    
                自己的子节点还要加上add（注意，add是给子节点用的，不是给自己用的。）
    
                那如果需要查找子节点的时候呢？
    
                那么我们就把子节点应该家的值加上去，并取消当前节点的值。
    
                注意，子节点也要被打上延迟标记，因为我们是修改了子节点的值，
    
                而子节点的子节点的值和子节点的子节点的子节点的值和子节点的子节点的子节点的子节点的值等等仍然没有修改。
    
            }
        }
    }

经过这么一分析，代码就总结出来了：

1 void spread(int t){ //取消延迟标记（标记下传）
     2     if(tree[t].mark)    //如果当前节点有标记
     3     {
     4         tree[t*2].val+=tree[t].mark*(tree[t*2].r-tree[t*2].l+1);    //更新左节点的值
     5         tree[t*2+1].val+=tree[t].mark*(tree[t*2+1].r-tree[t*2+1].l+1);  //更新右节点的值
     6         tree[t*2].mark+=tree[t].mark;   //左节点被打上标记
     7         tree[t*2+1].mark+=tree[t].mark; //右节点被打上标记
     8         tree[t].mark=0; //取消标记
     9     }
    10 }
    11 
    12 void change(int t,int x,int y,int k)
    13 {
    14     if(x<=tree[t].l && y>=tree[t].r)    //如果这个区间包含了待修改区间的一部分
    15     {
    16         tree[t].val+=(long long)k*(tree[t].r-tree[t].l+1);  //修改它的值
    17         tree[t].mark+=k;    //打上延迟标记
    18         return;
    19     }
    20     spread(t);  //延迟标记下传
    21     int mid=tree[t].l+tree[t].r>>1;
    22     if(x<=mid) change(t*2,x,y,k);   //修改左节点的值
    23     if(y>mid) change(t*2+1,x,y,k);  //修改右节点的值
    24     tree[t].val=tree[t*2].val+tree[t*2+1].val;      //由左节点和右节点推出当前节点的值。
    25 }

## 询问区间的值 ##

再来看一个例子：

查询\[2,6\]的值（区间和）：

![68832.png][]

查询本质上还是需要查找的。

而查找只是修改的一部分，所以查询操作比修改操作会简单很多的。

还是来看一看分析：

同修改一样，我们要找到涵盖了[2,6]的一部分的区间；
    {
        怎么找呢？我们还是递归查找左右节点，如果当前区间与要抄找的区间[2,6]完全没有交集，就停止递归。
    
        如果我们找到了一个区间被[2,6]所覆盖，我们就返回它的交集的每个元素的和，表示这是答案的一部分。
    
    }

思路还算是自然的。

然后贴上代码：

1 long long ask(int t,int x,int y)    //注意到数据大小
     2 {
     3     if(x<=tree[t].l && y>=tree[t].r) return tree[t].val;    //被要查找的区间所覆盖
     4     spread(t);  //为了递归子节点，就下传延迟标记
     5     int mid=tree[t].l+tree[t].r>>1;
     6     long long ans=0;
     7     if(x<=mid) ans+=ask(t*2,x,y);   //如果答案的一部分在左节点那边，就递归左节点
     8     if(y>mid) ans+=ask(t*2+1,x,y);  //如果答案的一本分在右节点那边，就递归右节点
     9 
    10      //注意：因为答案可能就是左边一部分，右边一部分，所以这两种情况是不矛盾的的，于是不用加上else；
    11     return ans;
    12 }

## main函数 ##

main函数完全是由着题意来得到的，应该没有思维难度。

int main(){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        bulid(1,1,n);
        while(m--)
        {
            int op,x,y,k;
            cin>>op;
            if(op==1)
            {
                cin>>x>>y>>k;
                change(1,x,y,k);
            }
            else
            {
                cin>>x>>y;
                cout<<ask(1,x,y)<<endl;
            }
        }
        return 0;
    }

# 最后贴上高清的Code: #

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 int a[100005];
     4 struct T
     5 {
     6     int l,r;
     7     long long val,mark;
     8 }tree[400005];
     9 void bulid(int t,int l,int r)
    10 {
    11     tree[t].l=l;tree[t].r=r;
    12     if(l==r)
    13     {
    14         tree[t].val=a[l];
    15         return;
    16     }
    17     int mid=l+r>>1;
    18     bulid(t*2,l,mid);
    19     bulid(t*2+1,mid+1,r);
    20     tree[t].val=tree[t*2].val+tree[t*2+1].val;
    21 } 
    22 void spread(int t){
    23     if(tree[t].mark)
    24     {
    25         tree[t*2].val+=tree[t].mark*(tree[t*2].r-tree[t*2].l+1);
    26         tree[t*2+1].val+=tree[t].mark*(tree[t*2+1].r-tree[t*2+1].l+1);
    27         tree[t*2].mark+=tree[t].mark;
    28         tree[t*2+1].mark+=tree[t].mark;
    29         tree[t].mark=0;
    30     }
    31 }
    32 
    33 void change(int t,int x,int y,int k)
    34 {
    35     if(x<=tree[t].l && y>=tree[t].r)
    36     {
    37         tree[t].val+=(long long)k*(tree[t].r-tree[t].l+1);
    38         tree[t].mark+=k;
    39         return;
    40     }
    41     spread(t);
    42     int mid=tree[t].l+tree[t].r>>1;
    43     if(x<=mid) change(t*2,x,y,k);
    44     if(y>mid) change(t*2+1,x,y,k);
    45     tree[t].val=tree[t*2].val+tree[t*2+1].val;   
    46 }
    47 long long ask(int t,int x,int y)
    48 {
    49     if(x<=tree[t].l && y>=tree[t].r) return tree[t].val;
    50     spread(t);
    51     int mid=tree[t].l+tree[t].r>>1;
    52     long long ans=0;
    53     if(x<=mid) ans+=ask(t*2,x,y);
    54     if(y>mid) ans+=ask(t*2+1,x,y);
    55     return ans;
    56 }
    57 
    58 int main(){
    59     int n,m;
    60     cin>>n>>m;
    61     for(int i=1;i<=n;i++)
    62         cin>>a[i];
    63     bulid(1,1,n);
    64     while(m--)
    65     {
    66         int op,x,y,k;
    67         cin>>op;
    68         if(op==1)
    69         {
    70             cin>>x>>y>>k;
    71             change(1,x,y,k);
    72         }
    73         else
    74         {
    75             cin>>x>>y;
    76             cout<<ask(1,x,y)<<endl;
    77         }
    78     }
    79     return 0;
    80 }

转载于:https://www.cnblogs.com/chengyurui/p/11297916.html

[Link 1]: https://www.luogu.org/problem/P3372
[Link 2]: https://baike.baidu.com/item/%E7%BA%BF%E6%AE%B5%E6%A0%91
[68817.png]: /images/20211029/089e196c74b84d6684cefbcdd977baf5.png
[68832.png]: /images/20211029/9fc6c841708d472e8bb002cae351abdf.png