线段树
Dfkuaid
·
2019-12-22 16:01:15
·
个人记录
引入：
我们经常会遇到需要维护一个序列的问题，例如，给定一个整数序列，每次操作会修改某个位置或某个区间的值，或是询问你序列中的某个区间内所有数的和。或许你可能回去暴力出奇迹或者使用前缀和，但是当数据很大时，时间复杂度明显是受不了的。那么，就需要引入一种时间复杂度相对较小的数据结构 ——线段树
目录
$\ \ \ \ \ \ \ \ \ \ \ \ $├ 关于线段树
$\ \ \ \ \ \ \ \ \ \ \ \ $├ 建树
$\ \ \ \ \ \ \ \ \ \ \ \ $├ 区间查询
$\ \ \ \ \ \ \ \ \ \ \ \ $└ 单点修改
$\ \ \ \ \ \ $**进阶**
$\ \ \ \ \ \ \ \ \ \ \ \ $├ 延迟标记
$\ \ \ \ \ \ \ \ \ \ \ \ $├ └ 区间修改 单点查询
$\ \ \ \ \ \ \ \ \ \ \ \ $└ 区间修改 区间查询
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $├ 标记下传
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $└ 标记永久化
---
###### 注：本文用到了位运算优化常数，不会的小伙伴可看这篇博客[【Portal】](https://www.cnblogs.com/shawnChi/p/5952045.html)
---
### Ⅰ 基础篇
#### 一、关于线段树
线段树是一课二叉树树上的每一个结点对应序列的一段区间，如下图：
不难发现，根节点对应的区间时$[0,n-1]$，而每个结点对应一个区间$[l,r]$，且当 **$l=r$** 时，该结点为**叶结点**，无左右儿子，否则令 $mid = (l + r) / 2 $,则左儿子对应的区间为$[l,mid]$，右儿子为$[mid+1,r]$。同时，也不难发现，最后一行有$n$个结点，倒数第二行有$n/2$个结点，倒数第三行有$n/4$个结点，以此便可以推出一个线段树有$n+\dfrac{n}{2}+\dfrac{n}{4}+...+1=2 \times n+1$个结点，但是要注意，线段树数组务必要开$4$倍。设线段树的深度为$h$，那么$h$为$O(\log n)$级别，当我们需要维护的序列长度为**2的整数次幂**时，这个线段数为**满二叉树**，否则最后一层可能不满
#### 二、建树
###### 注：接下来的一系列操作都以求区间和为例
设序列$a:5,3,7,9,6,4,1,2$，我们将其用线段树构建出来，即
从图中可以看出除叶结点区间和为它本身外，其他节点的区间和均为其左右儿子区间和之和。以此，可以通过递归建树，并在递归后对其区间和进行维护
``` cpp
void build(int k,int l,int r){ //k为结点编号，l为区间左端点，r为区间右端点
if (l == r){ //如果该点为叶结点
sum[k] = a[l]; //区间和即为本身
return;
}
int mid = l + r >> 1; //取中间值，位运算优化常数
build(k << 1,l,mid); //构建左子树
build(k << 1 | 1,mid + 1,r); //构建右子树
sum[k] = sum[k << 1] + sum[k << 1 | 1]; //维护该区间区间和
}
```
#### 三、区间查询
如果我们要查询区间和$[0,6]$，那么我们需访问3个区间
那么在查询过程中，会有以下三种情况
├ 当前区间与需查询区间**无交集**，返回 **0**
├ 当前区间被需查询区间**完全包含**，返回该结点**对应区间和**
└ 当前区间与需查询区间**有交集，但不被完全包含**，**递归其左右子树**进行查询
``` cpp
int query(int k,int x,int y,int l,int r){ //k为结点编号，x为当前区间左端点，y为当前区间右端点，
//l为需查询区间左端点，r为需查询区间右端点
if (x > r || y < l) return 0; //如果无交集，返回0
if (x >= l && y <= r) return sum[k]; //如果完全包含，返回该结点区间和
int res = 0,mid = x + y >> 1;
res = query(k << 1,x,mid,l,r); //递归左子树
res += query(k << 1 | 1,mid + 1,y,l,r); //递归右子树
return res;
}
```
#### 四、单点修改
假设要将$a_1$加2，那么我们要重新计算**4个结点**的值
变成
那么，在修改时可以用递归的形式修改
在递归中，可能会有以下几种情况
├ 当前区间**不包括**需修改区间，**直接返回**
├ 找到**需修改的叶结点**，修改，返回
└ 有包含，但**不是叶结点**，递归修改左右子树
``` cpp
void change(int k,int l,int r,int p,int v){
if (l > p || r < p) return; //若该区间不包含需修改点，直接返回
if (l == r && l == p){ //若当前即为需修改结点
sum[l] += v; //修改
return;
}
int mid = l + r >> 1;
change(k << 1,l,mid,p,v);//递归修改左子树
change(k << 1 | 1,mid + 1,r,p,v);//递归修改右子树
sum[k] = sum[k << 1] + sum[k << 1 | 1];//维护区间和
}
```
---
### Ⅱ 进阶篇
#### **一、延迟标记**
有时我们需要解决的不只是单点修改、区间询问，而是区间修改、区间询问，那么单纯使用以上的方法已经无法解决问题了，因为我们没有办法高效完成区间修改
以区间内所有数同时加上一个值，以及单点询问为例进行引入
**区间修改，单点查询**
考虑在每个结点上维护一个值$addsum$，表示这个结点所对应的区间内的所有数都加上了$addsum$。注意到根节点到叶结点$[i,i]$的路径会经过所有包含点$[i,i]$的区间对应结点，并且路径上所有结点都包括$[i,i]$这个点，所以路径经过的所有结点的$addsum$的值加起来便是当前结点的值
**1）区间修改**
我们还是采用递归的方式，对所求区间进行修改，我们在递归时，会遇上以下几种情况：
├ 当前区间不包括所修改区间，直接返回
├ 需修改区间完全包含当前区间，给当前区间的addsum加上需加的值
└ 否则对该结点的两个子树进行递归
``` cpp
void modify(int k,int l,int r,int x,int y,int v){//给区间[x,y]加上v
if (l > y || r < x) return; //无交集，直接返回
if (l >= x && r <= y){//完全包含
addsum[k] += v;
return;
}
int mid = l + r >>1;
modift(k << 1,l,mid,x,y,v);//递归左子树
modift(k << 1 | 1,mid + 1,r,x,y,v);//递归右子树
}
```
**2）单点查询**
在查询时，要从根结点查询至目标结点，会有以下几种情况
├ 当前为叶子结点（需查询结点），返回当前结点的addsum值
├ 目标结点编号小于等于当前结点对应区间的中点编号，说明目标结点在左子树，返回递归左子树得到的值加上该点的
$\ \ $ │ $addsum
└ 否则说明在右子树，返回递归右子树得到的值加上该点的addsum
int query(int k,int l,int r,int p){
if (l == r) return addsum[k];
int mid = l + r >> 1;
if (p <= mid)
return query(k << 1,l,mid,p) + addsum[k];
else
return query(k << 1 | 1,mid + 1,r,p) + addsum[k];
}再回到区间修改区间查询这一问题上，此时打标记的方法也不可用了，若是遍历所有会产生影响的结点并将其加起来，复杂度无法接受标记下传 ，二是标记永久化 。这俩兄弟有个非常nb的名字——Lazy-Tag （懒标记）
二、区间修改 区间查询 1）标记下传 add(addsum) ，并且得到更新的sum 值，而这个结点所有的祖先都能通过 sum_{k}=sum_{k \times 2}+sum_{k \times 2+1} 得到当前修改后正确的区间和，而这个结点的子节点无法立即更新，因为这样的子节点太多，所以时间复杂度他又炸了。。。（敲黑板） ：当我们用到这些子结点的信息时再进行更新，其实就是在某个结点递归下去，将当前节点的add 下传到两个子结点，更新两个子结点的sum 和add ，并将当前结点的add 清零。这样操作以后，当我们访问一个节点时，根节点到他的路径上的add 值都已经下传更新到它的sum 上了，所以它的sum 便是它对应的区间和。1 》 打标记（这里这是单纯的打标记） 疫检合格了（不是sum_{k} += (r-1+1) \times v
void Add(int k,int l,int r,int v){
add[k] += v;
sum[k] += (r - l + 1) * v;
}2 》 标记下传 又双叒叕用递归实现，如果需下传的这个结点的add为0，跳出；否则下传至左右子树（其实就是调用一下刚刚的Add）
注意：记得将该点add清零！！！
void pushdown(int k,int l,int r,int mid){
if (add[k] == 0) return;
Add(k << 1,l,mid,add[k]);
Add(k << 1 | 1,mid + 1,r,add[k]);
add[k] = 0;
}3 》 区间修改 又双叒叕用递归实现；
void modify(int k,int l,int r,int x,int y,int v){
if (l >= x && r <= y) return Add(k,l,r,v);
int mid = l + r >> 1;
pushdown(k,l,r,mid);
if (x <= mid) modify(k << 1,l,mid,x,y,v);
if (mid < y) modify(k << 1 | 1,mid + 1,r,x,y,v);
sum[k] = sum[k << 1] + sum[k << 1 | 1];
}4 》 区间查询
int query(int k,int l,int r,int x,int y){
if (l >= x && r <= y)
return sum[k];
int mid = l + r >> 1;
int res = 0;
pushdown(k,l,r,mid);
if (x <= mid)
res += query(k << 1,l,mid,x,y);
if (mid < y)
res += query(k << 1 | 1,mid + 1,r,x,y);
return res;
}2）标记永久化
void modify(int k,int l,int r,int x,int y,int v){ //区间修改
if (l >= x && r <= y){
add[k] += v;
return;
}
sum[k] += (min(r,y) - max(l,x) + 1) * v;
int mid = l + r >> 1;
if (x <= mid) modify(k << 1,l,mid,x,y,v);
if (mid < y) modify(k << 1 | 1,mid + 1,r,x,y,v);
}
int query(int k,int l,int r,int x,int y){ //查询
if (l >= x && r <= y)
return sum[k] + (r - l + 1) * add[k];
int mid = l + r >> 1;
int res = (min(r,y) - max(l,x) + 1) * add[k];
if (x <= mid)
res += query(k << 1,l,mid,x,y);
if (mid < y)
res += query(k << 1 | 1,mid + 1,r,x,y);
return res;
}验证题目：【P3372】
如果您有什么见解或疑问，欢迎在评论区提出(￣▽￣)／