线段树（超详解）
Author ：铜陵一中 缪语博
在网上看了几个讲线段树的，都感觉不咋地，自己琢磨了几天，大致弄明白了。于是趁兴写了一篇关于线段树的文章，希望拯救那些看 o i − w i k i oi-wiki oi−wiki看不懂的 o i e r oier oier。
前言
在阅读本文之前，你需要明确：
- 本人码风可能与你不同，请多谅解。
- 有可能我的代码用到什么 d e f i n e define define可能和晚上的“简单”违背，请不要误解。写多了你就会知道，这样写真的很方便。
命名规则：
- p p p：当前的线段树的节点。
- l , r l,r l,r：当前线段树的左右区间范围。
- q l , q r ql,qr ql,qr：目标线段树的左右区间范围。
C h a p t e r 1 Chapter 1 Chapter1 干嘛要用线段树？
Put simply，就是区间操作。题目中出现区间，大概率就是线段树了。有人问：我直接一个数组不就行了吗？
N o ， N o ， N o ， s l o w ！ No，No，No，slow！ No，No，No，slow！
假设有 1 0 6 10^6 106个操作，每一次操作你都要修改，求和，求最大值，更新
T L E ！ TLE！ TLE！
线段树就是来解决这个问题的。
但是为什么呢？
一个类似前缀和的思想。思考这样一个问题：假如你做人口普查，铜陵市政府统计了铜陵市的人口。现在安徽省政府来统计，还需要统计铜陵市的人口吗？
显然不需要，直接把铜陵市政府的数据拿来用不就行了吗？
同理，你已经算出了某个区间的数据，你直接拿来用就可以了，干嘛还要再算一遍？你是嫌 1 s 1s 1s的时间限制短了？
那么问题来了，怎么操作呢？
C h a p t e r 2 Chapter 2 Chapter2 什么是线段树？怎么建线段树？
在学习之前，你得有一些树的基本知识，比如说：
- 什么是树（废话）。
- 在一棵完全二叉树中（根节点编号为 1 1 1），节点 p p p的左儿子的编号为 2 p 2p 2p，右儿子的编号为 2 p + 1 2p+1 2p+1。
先来了解一下线段树为什么快。
试问：怎么查找最快？
二分。
对！线段树就可以理解为“二分”，二分区间，这样查找就会变得很快，直降 O ( l o g n ) O(logn) O(logn)
这样，我们就可以开始建树了。
建树过程（OI-Wiki上写得已经够详细了，移步一下吧）。
好的，默认你已经知道了线段树长什么样子了。
对于一个非叶子节点 p p p，其均有一个左子树和右子树，刚刚才讲过，左儿子的编号为 2 p 2p 2p，右儿子的编号为 2 p + 1 2p+1 2p+1。
为了方便起见，我们使用 d e f i n e define define来简便定义左子树和右子树。
#define ls (p << 1)
#define rs (p << 1 | 1)
- 其中，
(p << 1)和(p << 1 | 1)的意思分别是 2 × p 2\times p 2×p和 2 × p + 1 2\times p + 1 2×p+1，这样定义更加简便快速。
于是我们开始建树。
首先，对于一个区间 [ l , r ] [l,r] [l,r]，如果访问时， l = r l = r l=r，那么其就是叶子结点，否则就不是叶子结点（废话）。我习惯于将 l , r l,r l,r放在参数里传递，而不是用结构体来定义，我认为这样可能会简便一些。
有人问：那节点的区间长度如何定义叻？
用一个siz数组不就行了吗？
以建立一棵求区间和的线段树为例。
- 这里还有一个定义，就是
m
i
d
mid
mid的定义，也使用宏定义：
#define mid ((l + r) >> 1)
#define N 100001
#define ll long long
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)
int n, m;
int a[N];
ll tree[N << 2];
int siz[N << 2];
int lazy[N << 2];
void build(int p, int l, int r) {
lazy[p] = 0;
if(l == r) {
return ;
}
build(ls, l, mid);
build(rs, mid + 1, r);
}
- 这里的 l a z y lazy lazy数组你暂时可以不用管，这是以后要讲到的。
C h a p t e r 3 Chapter 3 Chapter3 线段树的初始化
简单了，加几行就行了。
首先是叶子结点的数据，直接放区间（节点）所对应的值就好了。
然后是非叶子结点的维护，用一个upd函数来更新tree的值，用一个upds函数来更新siz的大小。
void upd(int p) {
tree[p] = tree[ls] + tree[rs];
}
void upds(int p) {
siz[p] = siz[ls] + siz[rs];
}
void build(int p, int l, int r) {
lazy[p] = 0;
if(l == r) {
siz[p] = 1;
tree[p] = a[l];
return ;
}
build(ls, l, mid);
build(rs, mid + 1, r);
upd(p);
upds(p);
}
C h a p t e r 4 Chapter 4 Chapter4 线段树的查询
还是以建立一棵求区间和的线段树为例。
泰见但辣！
如果当前的区间 [ l , r ] [l,r] [l,r]被完全包含于查询区间 [ q l , q r ] [ql, qr] [ql,qr]，直接加和即可。
如果没有被完全包含，拆成它的左子树和右子树，不断缩小范围就行了。
这里理解一个问题：我怎么知道应该拆左子树还是拆右子树？
比如说，当有这样一种情况：
[ l , r ] = [ 4 , 7 ] [l,r]=[4,7] [l,r]=[4,7]， [ q l , q r ] = [ 3 , 5 ] [ql,qr]=[3,5] [ql,qr]=[3,5]
发现没有被完全包含，其中， q r ≥ l qr \geq l qr≥l，所以可以看它的左子树和右子树。如果左子树满足条件，就既搜左子树，又搜右子树，反复递归，直至区间被完全覆盖。如果只有右子树满足条件，就只搜右子树，直至区间被完全覆盖。
ll qry(int p, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) {
return tree[p];
}
ll sum = 0;
if(ql <= mid) {
sum += qry(ls, l, mid, ql, qr);
}
if(qr > mid) {
sum += qry(rs, mid + 1, r, ql, qr);
}
return sum;
}
C h a p t e r 5 Chapter 5 Chapter5 懒标记
很重要的一部分，一定要反复看，比较难理解。
什么是懒标记？
就是懒（废话）。
为什么？
想一想，如果我每一次增加区间的值，每一次更新都全部下放到子树，那时间复杂度就是无法估量的。所以，只有碰到查询时，或者要更改这个区间的一部分的时候才会全部下放到子树，并且是下放到儿子结点，这样做会更快（想一想，为什么）。
定义： l a z y [ p ] lazy[p] lazy[p]表示当结点 p p p的 t r e e tree tree值已经更新时，其儿子结点还没有下放的数值。可能很少有文章强调当结点 p p p的 t r e e tree tree值已经更新时，但是这个地方理解很重要！这样可以使你的思路更加清晰。
于是，我们得到了一个下放结点 p p p的懒标记的代码：
void pushd(int p) {
tree[ls] += lazy[p] * siz[ls];
tree[rs] += lazy[p] * siz[rs];
lazy[ls] += lazy[p];
lazy[rs] += lazy[p];
lazy[p] = 0;
}
在更新中的具体代码下节讲，在查询中的放在结尾的代码里，自行理解。
C h a p t e r 6 Chapter 6 Chapter6 更新区间
还是以上面那个例子为例（有语病吗？），更新区间是将区间内所有的值加 k k k。
现在就很好理解了。
- 如果当前结点被完全覆盖，直接将 t r e e tree tree值加上 s i z [ p ] × k siz[p] \times k siz[p]×k即可。
- 如果没有，继续拆。
- 注意下放懒标记！
void mdf(int p, int l, int r, int ql, int qr, int k) {
if(ql <= l && r <= qr) {
tree[p] += 1ll * siz[p] * k;
lazy[p] += k;
return;
}
pushd(p);
if(ql <= mid) {
mdf(ls, l, mid, ql, qr, k);
}
if(qr > mid) {
mdf(rs, mid + 1, r, ql, qr, k);
}
upd(p);
}
C h a p t e r 7 Chapter 7 Chapter7 终章 C o d e Code Code
#include <bits/stdc++.h>
#define N 100001
#define ll long long
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;
int n, m;
int a[N];
ll tree[N << 2];
int siz[N << 2];
int lazy[N << 2];
void upd(int p) {
tree[p] = tree[ls] + tree[rs];
}
void upds(int p) {
siz[p] = siz[ls] + siz[rs];
}
void pushd(int p) {
tree[ls] += lazy[p] * siz[ls];
tree[rs] += lazy[p] * siz[rs];
lazy[ls] += lazy[p];
lazy[rs] += lazy[p];
lazy[p] = 0;
}
void build(int p, int l, int r) {
lazy[p] = 0;
if(l == r) {
siz[p] = 1;
tree[p] = a[l];
return ;
}
build(ls, l, mid);
build(rs, mid + 1, r);
upd(p);
upds(p);
}
void mdf(int p, int l, int r, int ql, int qr, int k) {
if(ql <= l && r <= qr) {
tree[p] += 1ll * siz[p] * k;
lazy[p] += k;
return;
}
pushd(p);
if(ql <= mid) {
mdf(ls, l, mid, ql, qr, k);
}
if(qr > mid) {
mdf(rs, mid + 1, r, ql, qr, k);
}
upd(p);
}
ll qry(int p, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) {
return tree[p];
}
pushd(p);
ll sum = 0;
if(ql <= mid) {
sum += qry(ls, l, mid, ql, qr);
}
if(qr > mid) {
sum += qry(rs, mid + 1, r, ql, qr);
}
return sum;
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
build(1, 1, n);
while(m--) {
int op, x, y, k;
cin >> op >> x >> y;
if(op == 1) {
cin >> k;
mdf(1, 1, n, x, y, k);
}
else {
cout << qry(1, 1, n, x, y) << endl;
}
}
return 0;
}
也希望看完这篇文章的你能点一个大大的赞，给一个大大的支持！
完结撒花！
标签：lazy,qr,int,线段,tree,mid,详解,ql From： https://blog.csdn.net/MYB20091111/article/details/142864846