数据结构之线段树入门

一、前言

对于维护区间连续和问题，我们已经学了很多种算法和数据结构，在规定n<=100000,m(操作数)<=200000,内，暴力算法可以解决单点修改，单点求值。前缀和算法可以解决区间求和问题，而最近学的树状数组可以解决单点修改，区间求和的问题。而当我们需要区间修改时，上边的三种算法都将失效，我们亟待引入一个新的数据结构——线段树。

二、线段树基本思想

1.线段树是一棵二叉树，每一个子节点存取的是一段区间所需要维护的信息，如最大值，最小值，或区间和。

2.线段树基本思想：分治

3.线段树每个节点都以结构体的方式存储，这个结构体有4个属性：左端点、右端点、所维护的信息以及LazyTag(后面会详细说明)

下图很好地阐释了线段树储存信息的方式：

当我们需要求1-3区间和时，只需要调取1-2段和3段的信息即可，具体如何调取将会在以下说明。

注：以下维护信息均为区间和。

三、线段树五大基本操作之一 —— 建树

线段树的建树过程实际上是自底向上计算初始值的过程，从顶向下递归，如果是叶子节点那么就输入值，输入完毕后回溯时计算父节点的权值。

线段树建树代码如下：（注意：一定要把结构体开到4*n级别，手画一棵线段树就知道了！）

 1 void build(int l,int r,int k)
 2 {
 3     tree[k].l=l;tree[k].r=r;
 4     if(l==r)
 5     {
 6         scanf("%lld",&tree[k].w);
 7         return;
 8     }
 9     int mid=(l+r)/2;
10     build(l,mid,k*2);
11     build(mid+1,r,k*2+1);
12     tree[k].w=tree[k*2].w+tree[k*2+1].w;
13 }

View Code

四、线段树五大基本操作之二 —— 单点查询

由于线段树一个非叶节点的两棵子树储存的是这个区间的一半，我们可以根据这个特点每次对范围进行一半的缩小，直到递归到叶子节点为止。时间复杂度为log(n)

线段树单点查询代码如下：

1 int query_point(int k)
2 {
3     int l=tree[k].l,r=tree[k].r;
4     if(l==r)return tree[k].w;
5     int mid=(l+r)/2;
6     if(x<=mid)return query(k*2);
7     return query(k*2+1);
8 }

View Code

五、线段树五大基本操作之三 —— 单点修改

单点修改和单点查询原理一样，只需在回溯时维护一下信息即可。

线段树单点修改代码如下：

 1 void add_point(int k,int w)
 2 {
 3     int ll=tree[k].l,rr=tree[k].r;
 4     if(ll==rr)
 5     {
 6         tree[k].w+=w;
 7         return;
 8     }
 9     int mid=(ll+rr)/2;
10     if(x<=mid)add(k*2,w);
11     else add(k*2+1,w);
12     tree[k].w=tree[k*2+1].w+tree[k*2].w;
13     return;
14 }

View Code

六、线段树五大基本操作之四 —— 区间求和

区间求和依旧是根据线段树的特点，尽可能调用深度较浅的节点，当目前区间被所需区间完全覆盖时，就加上，否则继续递归。

线段树区间求和代码如下：

 1 int query_interval(int k)
 2 {
 3     int l=tree[k].l,r=tree[k].r;
 4     if(l>=x&&r<=y)
 5     {
 6         ans+=tree[k].w;
 7         return;
 8     }
 9     int mid=(l+r)/2;
10     if(x<=mid)query(k*2);
11     if(y>mid)query(k*2+1);
12 }

View Code

六、线段树之LazyTag

使用线段树的一个重要目的就是进行区间修改，而如果按照单点修改的思路，修改整个区间时将会修改整棵线段树，比朴素算法还劣，这时我们就需要引入LazyTag(懒标记)，顾名思义，懒标记十分的懒，只在需要的时候下放，否则就一直呆着。为什么不能一下就全都修改呢？是因为我们其实有很多不需要的信息被下放了，因此造成TLE。因此采用LazyTag改动尽量少点的权值，并改动LazyTag的值，在进行递归的时候为了保证正确性需要先改动子节点的值，该操作叫做标记下放(pushdown),标记下放的时候直接下放到k*2和k*2+1中，并累积到权值和当前节点的LazyTag里（一定要累积，在该节点下放之前父节点可能不止一次下放）注意：在使用LazyTag的程序中，五种基本操作在递归前都需要pushdown！！！

pushdown代码如下：

1 void pushdown(int k)
2 {
3     tree[k*2].lazytag+=tree[k].lazytag;
4     tree[k*2].w+=(tree[k*2].r-tree[k*2].l+1)*tree[k].lazytag;
5     tree[k*2+1].lazytag+=tree[k].lazytag;
6     tree[k*2+1].w+=(tree[k*2+1].r-tree[k*2+1].l+1)*tree[k].lazytag;
7     tree[k].lazytag=0; 
8     return;
9 }

View Code

七、线段树五大基本操作之五 —— 区间修改

有了LazyTag，区间修改代码不难写出，和区间求和代码思路一样，需要的时候标记下放即可

线段树区间修改代码如下：

 1 void add(int k,int w)
 2 {
 3     int ll=tree[k].l,rr=tree[k].r;
 4     if(ll>=x&&rr<=y)
 5     {
 6         tree[k].w+=(rr-ll+1)*w;
 7         tree[k].lazytag+=w;
 8         return;
 9     }
10     if(tree[k].lazytag)pushdown(k);
11     int mid=(ll+rr)/2;
12     if(x<=mid)add(k*2,w);
13     if(y>mid)add(k*2+1,w);
14     tree[k].w=tree[k*2].w+tree[k*2+1].w;
15     return;
16 }

View Code

线段树五种基本操作及LazyTag非常重要，请大家一定要好好理解！！

如果你喜欢我的博客，别忘了点个赞哦~~~