[算法学习笔记01]线段树

# [算法学习笔记01]线段树
### 每日蒟蒻小故事(1/1)
蒟蒻刚刚升到S组，发现S组正在学习线段树Ⅲ.

蒟蒻并不知道什么是线段树.

蒟蒻十分害怕，向大佬询问什么是线段树.

大佬邪魅一笑，并未解释.

于是可怜的蒟蒻什么也听不懂，只得在洛谷和OI WIKI上自学线段树.

“所以什么是线段树？”
### 什么是线段树？
线段树是算法竞赛中常用的用来维护**区间信息**的数据结构。

一般来说，它可以：

1. 查询某个区间

2. 修改某个区间或点

线段树将每个长度不为 $1$ 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。

“其实感觉没啥用.”蒟蒻说.

不，你错了！它的用处很大，对于所有区间的问题，他几乎都可以快速解决。

“真的假的？那怎么建树呢？”
### 怎么建树？
有个大小为 5 的数组 $a={10,11,12,13,14}$ ，要将其转化为线段树，有以下做法：设线段树的根节点编号为 $1$，用数组 $d$ 来保存我们的线段树，$di$ 用来保存线段树上编号为 $i$ 的节点的值（这里每个节点所维护的值就是这个节点所表示的区间总和）。

我们先给出这棵线段树的形态，如图所示：


(图片来自OI WIKI)

我们可以清楚地通过上图发现线段树的每个子节点都是由它的父亲节点二分而来的，再通过二叉树的性质，我们可以知道对于一个父节点$i$，它的左右儿子节点分别为 $2i$ 和 $2i+1$ 。

所以我们可以根据这个性质用数组来模拟线段树，代码如下。

```cpp
void build(int id,int l,int r){
tree[id].l=l;
tree[id].r=r;
if(l==r){
tree[id].sum=a[l];
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
```
蒟蒻看到一连串的代码十分开心，连忙将其Ctrl+c+v提交到[题目](https://www.luogu.com.cn/problem/P3372)里。

竟然是 WA ！

蒟蒻十分生气，质问道：“为什么成功不了？”

你还没有区间更新呢！相当于是你只写了四分之一的代码啊！

“那怎么解决区间更新？”
### 怎么解决区间更新？
如果我们要对这颗树上的区间加上 v ，是不是只用找到代表这个区间的节点（可能不止一个节点，例如[2,3]这个区间就需要查找[2,2]和[3,3]这两个区间，然后将他们的 sum 加起来），然后将这个节点的sum值加上v乘以这个区间所包含的数的个数？下次访问相同的区间的时候直接将这个数返回过去，根本就不用再向下遍历了。

但是问题又来了，上一次我对[1,2]这个区间加了 v ，这一次我想知道[2,3]的区间和怎么办呢？要是只用我们上面提到的方法，很明显遍历到[2,2]的时候这个点并没有加v，那返回时答案就错了呀！

怎么办？

这时延迟标记（ lazy ）就派上用场了，它代表我对这个区间的数加过的值，我们在对一个区间加了 v 之后，我们将 lazy 的值也加上这个 v ，后来我们再访问这个区间但只是访问这个区间的一部分时我们就可以知道这个父节点下面的儿子节点需要加上多少了，但我们现在不用急着将这个 lazy 标记给它的儿子们加上，因为这很费时，当我们下次将要访问它的儿子节点时再给他们加上 lazy 标记，此时这个父节点的 lazy 值就要清零，我们就称其为标记下传。

举个例子：我们在访问[2,3]时，我们会访问[2,2]和[3,3]这两个节点，将要访问[2,2]时，我们肯定会访问[1,2]这个点，那么在向下遍历的同时，我们就顺便将 lazy 标记下传，下传时就把每个叶子节点的 lazy 加上这个值，再按之前说到的方法更新 sum 。如此反复。

代码则在这：

```cpp
void down(int id){
tree[id*2].lazy+=tree[id].lazy;
tree[id*2].sum+=(tree[id*2].r-tree[id*2].l+1)*tree[id].lazy;
tree[id*2+1].lazy+=tree[id].lazy;
tree[id*2+1].sum+=(tree[id*2+1].r-tree[id*2+1].l+1)*tree[id].lazy;
tree[id].lazy=0;
}
void update(int id,int l,int r,int v){
if(tree[id].l>r || tree[id].r<l) return;
if(tree[id].l>=l && tree[id].r<=r){
tree[id].lazy+=v;
tree[id].sum+=(tree[id].r-tree[id].l+1)*v;
return;
}
if(tree[id].lazy>0) down(id);
update(id*2,l,r,v);
update(id*2+1,l,r,v);
tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
```

蒟蒻高兴地复制代码。

还是 WA !

“为什么！！！”

这只是两个片段啊！要结合起来才能使用！

“那赶快总结！”
### 快速总结一下！
其实就分为这么两大步：

>1.判断访问区间和遍历区间的关系（相离，部分相交，完全包含）

>>如果相离，直接返回。

>>如果部分相交，那么就需要将标记下传（如果有），然后向下找完全包含的区间。

>>如果完全包含，更新 lazy 标记，并且将 sum 更新（因为当前不会再向下，所以不能通过左右儿子的 sum 来计算）要按代码那样计算（也就是将这个节点的 sum 值加上 v * 这个区间所包含的数的个数）

>>在更新时一定要标记下传！

>2.标记下传

>>先下传到左儿子，再下传到右儿子

>>下传时你需要更新儿子节点的 lazy （因为它还可能有儿子，下次遍历它的儿子时要继续下传）和它的 sum （与1中的 sum 更新方法相同）

>>最后，将自己的 lazy 标记清空（否则会重复下传，造成答案错误）

“还有什么吗？”

还有最后一步，查询！

其实查询原理差不多，那就直接上查询代码啦！

```cpp
long long query(int id,int l,int r)
{
if(tree[id].l>r || tree[id].r<l) return 0;
if(tree[id].l>=l && tree[id].r<=r) return tree[id].sum;
if(tree[id].lazy>0) down(id);
return query(id*2,l,r)+query(id*2+1,l,r);/
}
```
“所以结合代码呢？”

蒟蒻怒目圆睁。

别急啊，这不就来了吗！
```cpp
#include<cstdio>
using namespace std;
int n,m,a[100010];
struct llk{
long long l,r,lazy,sum;
}tree[500010];
void build(int id,int l,int r){
tree[id].l=l;
tree[id].r=r;
if(l==r){
tree[id].sum=a[l];
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
void down(int id){
tree[id*2].lazy+=tree[id].lazy;
tree[id*2].sum+=(tree[id*2].r-tree[id*2].l+1)*tree[id].lazy;
tree[id*2+1].lazy+=tree[id].lazy;
tree[id*2+1].sum+=(tree[id*2+1].r-tree[id*2+1].l+1)*tree[id].lazy;
tree[id].lazy=0;
}
void update(int id,int l,int r,int v){
if(tree[id].l>r || tree[id].r<l) return;
if(tree[id].l>=l && tree[id].r<=r){
tree[id].lazy+=v;
tree[id].sum+=(tree[id].r-tree[id].l+1)*v;
return;
}
if(tree[id].lazy>0) down(id);
update(id*2,l,r,v);
update(id*2+1,l,r,v);
tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
long long query(int id,int l,int r){
if(tree[id].l>r || tree[id].r<l) return 0;
if(tree[id].l>=l && tree[id].r<=r) return tree[id].sum;
if(tree[id].lazy>0) down(id);
return query(id*2,l,r)+query(id*2+1,l,r);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,1,n);
for(int i=1;i<=m;i++){
int o,x,y;
scanf("%d",&o);
if(o==1){
int k;
scanf("%d%d%d",&x,&y,&k);
update(1,x,y,k);
}
else {
scanf("%d%d",&x,&y);
printf("%lld\n",query(1,x,y));
}
}
}
```
### 最后的故事

蒟蒻高兴地复制代码提交了。

喂，你要不要脸啊！

“怎么能诬陷人呢！这是我学了之后自己写的！”

蒟蒻骄傲地又写了一遍代码。

看来你学会了啊！

“嗯！我离 AK IOI 的梦想，又近了一步呢！”

# 全文·完