线段树笔记
jins3599
·
·
题解
定义
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。
线段树的作用&可以支持的操作
作用:
理论上所有符合结合律的东西都可以用线段树维护。
例如，区间和，区间乘积，区间max/min值……还有很多很奇怪的东西都可以用线段树维护。
操作：
区间修改查询，单点修改查询。
我们这里以区间和为例.
1.建树与维护
由于线段树是一颗完全二叉树,则有下面的性质:
对于每个父亲节点的编号P ,他的两个儿子的编号分别是2*P和2*P+1。
我们都知道 << 代表的是二进制下左移一位，相当于*2.
所以 左儿子 = P*2 = P<<1;
由于 P<<1 后最后一位空出，为0，则 P<<1|1 就代表了P*2 + 1；
综上,我们对于结点P,他的左右儿子在二进制下的表示为：
$rson(P) = P<<1|1$;
用宏和函数都可以.
```cpp
define lson(x) x<<1
define rson(x) x<<1|1
```
树的存储:
存储的方式有两种
1.结构体存储。
2.用数组直接存。
两种存储的方式没有本质的不同，时间复杂度一样，不过我比较推荐大家用结构体.
代码如下:
```cpp
struct _tree{
int l,r,add,pre;
}tree[maxn << 2];
```
从线段树的图中我们可以看出除叶子外每个节点的信息都是由它的子节点向上合并而来。
因此我们可以得到线段树的维护：
```cpp
inline void pushup(int x){
tree[x].pre = tree[lson(x)].pre + tree[rson(x)].pre;
}
```
简单的来说，就是把当前结点左右儿子的信息进行合并。
这被我们称为 pushup 操作。
我们在这儿就能看出来，实际上 pushup 是在合并两个子节点的信息，
所以需要信息满足结合律！
### 小结:
（1） 维护父子关系。
对于建树，由于二叉树自身的父子节点之间的可传递关系，所以可以 考虑递归建树。在建树的同时维护父子节点关系。
由于我们是用自己的儿子来更新自己的信息，因此要在儿子更新之后 再合并成为父亲的信息。
对于递归来说，就很显然了，我们需要再回溯的时候用刚才讲的 pushup 操作。
（2）分配结点所涵盖的区间。
还是对于刚开始的那个图,两个儿子的区间加在一起为父亲的区间。
因此我们在建树的时候，对于每个父区间，我们找到他的mid ,左边 部分分配给左儿子，右边部分分配给右儿子.
最后当到达叶子结点的时候，把单个的结点值更新，回溯时向上 pushup,合并区间信息。
代码的具体实现在后面。
```cpp
inline void built(ll p,ll l,ll r){
tree[p].l=l,tree[p].r = r;
if(l==r){
tree[p].pre = a[r];
return;
}
ll mid = (l+r) >> 1;
built(lson(p),l,mid);
built(rson(p),mid+1,r);
pushup(p);
}
```
几个小细节。
第三行： if(l == r) 的意思是到达了叶子结点。(即包含的区间只有一个点时)
到达叶子结点的时候更新单点，别忘了写return
## 2.区间查询。
#### Q:First ,为啥不先讲单点查询？
#### A:因为单点查询时区间查询的一种特殊情况啦!
经过前面对线段树的理解，相信进行区间查询这种操作对大家已经不是什么问题。
原理就是 如果查到的当前区间被 要查询的区间 “完全包含”,就用ans += 当前区间的值,return;(以维护区间和为例
```cpp
inline ll ask(ll p,ll l,ll r){
if(l<=tree[p].l && r>=tree[p].r) return tree[p].pre;
pushdown(p);
ll mid = (tree[p].l + tree[p].r) >> 1;
ll sum = 0;
if(l <= mid) sum += ask(lson(p),l,r);
if(r > mid) sum += ask(rson(p),l,r);
return sum;
}
```
欸？里面的pushdown是啥捏？
别慌，我们接着就会讲.
## 3.区间修改
这是线段树中的一个难点，也是一个重点。
我们首先考虑不加任何优化的暴力修改。
依旧是这个图。
如果我们要修改区间$[1,5]$,暴力修改的话需要$O(9)$的复杂度。
而直接修改只需要$O(5)$的复杂度，如果这样，线段树就没有任何优势了。
所以，我们引入了一个新的东西.
## Lazy tag.
之所以称其“lazy”，是因为原本区间修改需要通过先改变叶子节点的值，然后不断地向上递归修改祖先节点直至到达根节点，时间复杂度最高可以到达 O(nlogn) 的级别。但当我们引入了懒标记之后，区间更新的期望复杂度就降到了O(logn) 的级别且甚至会更低.
懒标记的思想精髓在于下面这句话(我瞎jier总结的..
#### 每次修改只修改公共祖先。
#### 每次用到该点的时候下放lazytag.
so that ，问题来了，怎么下放lazytag?
与pushup相对应 ， 我们称为pushdown.
我们知道 , pushup是合并两个儿子的信息给父亲
相对应的 pushdown 是把 父亲的信息传递给儿子.
传递lazytag的时候，我们要把tag传递给儿子，还要记得修改儿子的值。
我们还是以简单的区间和为例子。
```cpp
inline void pushdown(ll p){
if(tree[p].add!=0){
ll tot = tree[p].add;
tree[lson(p)].pre += tot*(tree[lson(p)].r-tree[lson(p)].l+1);
tree[rson(p)].pre += tot*(tree[rson(p)].r-tree[(rson(p))].l+1);
tree[lson(p)].add += tot;
tree[rson(p)].add += tot;
tree[p].add = 0;
}
}
```
会了lazy_tag，你就可以轻松的进行区间修改操作了…
(线段树的主体基本相同，每道题目的不同之处主要是在于 pushup() 和
pushdown() 函数的构造。
线段树change 代码如下:
```cpp
inline void change(ll p,ll l,ll r,ll w){
if(tree[p].l>=l && tree[p].r<=r){
tree[p].pre += w*(tree[p].r-tree[p].l+1);
tree[p].add += w;
return;
}
pushdown(p);
ll mid = (tree[p].l+tree[p].r) >> 1;
if(l<=mid) change(lson(p),l,r,w);
if(r>mid) change(rson(p),l,r,w);
pushup(p);
}
```
整个代码:
```cpp
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define lson(x) x<<1
#define rson(x) x<<1|1
typedef long long ll;
const int maxn=100010;
ll a[maxn];
ll n,m,x,o,b,c,d;
struct _tree{
ll l,r,add,pre;
}tree[maxn*4+5];
inline void pushup(ll x){
tree[x].pre = tree[lson(x)].pre + tree[rson(x)].pre;
}
inline void built(ll p,ll l,ll r){
tree[p].l=l,tree[p].r = r;
if(l==r){
tree[p].pre = a[r];
return;
}
ll mid = (l+r) >> 1;
built(lson(p),l,mid);
built(rson(p),mid+1,r);
pushup(p);
}
inline void pushdown(ll p){
if(tree[p].add!=0){
ll tot = tree[p].add;
tree[lson(p)].pre += tot*(tree[lson(p)].r-tree[lson(p)].l+1);
tree[rson(p)].pre += tot*(tree[rson(p)].r-tree[(rson(p))].l+1);
tree[lson(p)].add += tot;
tree[rson(p)].add += tot;
tree[p].add = 0;
}
}
inline void change(ll p,ll l,ll r,ll w){
if(tree[p].l>=l && tree[p].r<=r){
tree[p].pre += w*(tree[p].r-tree[p].l+1);
tree[p].add += w;
return;
}
pushdown(p);
ll mid = (tree[p].l+tree[p].r) >> 1;
if(l<=mid) change(lson(p),l,r,w);
if(r>mid) change(rson(p),l,r,w);
pushup(p);
}
inline ll ask(ll p,ll l,ll r){
if(l<=tree[p].l && r>=tree[p].r) return tree[p].pre;
pushdown(p);
ll mid = (tree[p].l + tree[p].r) >> 1;
ll sum = 0;
if(l <= mid) sum += ask(lson(p),l,r);
if(r > mid) sum += ask(rson(p),l,r);
return sum;
}
int main (){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i)
scanf("%lld",&a[i]);
built(1,1,n);
while(m--){
scanf("%lld",&o);
if(o==1){
scanf("%d%d%d",&b,&c,&d);
change(1,b,c,d);
}
if(o==2){
scanf("%d%d",&b,&c);
ll ans = ask(1,b,c);
printf("%lld\n",ans);
}
}
return 0;
}
```
希望大家可以提出不足！