蓝月の笔记——线段树篇
在树状数组中,我们讲解了关于单点修改区间查询的操作。今天,我们要讲一种更加高级的数据结构,他解决的是区间修改区间查询的问题多了一个区间当然更高级啦。
这个数据结构就是——线段树
给定一个长度为 \(n\) 的序列 \(a_1,a_2,\cdots,a_n\) 和两种操作:
- 输入
1 l r k
,将 \([l,r]\) 区间里的每一个数加上 \(x\); - 输入
2 l r
,求 \(\sum_{i=l}^{r}a_i\)。
这就是区间修改区间查询。
正片开始
先看图
【图片来源:OI-Wiki】
这就是线段树的建出来的树。所以我们就讲完了(逃
注意:线段树是一颗二叉树
所以讲解函数之前,我们要了解二叉树的子节点查看方法。
观察图,我可以看出:\(1\) 的子节点是 \(2(1 \times 2)\) 和 \(3(1 \times 2 + 1)\),\(2\) 的子节点是 \(4(2 \times 2)\) 和 \(5(2 \times 2 + 1)\),\(3\) 的子节点是 \(6(3 \times 2)\) 和 \(7(3 \times 2 + 1)\)。
以此类推,我们知道:编号为 \(i\) 的非叶子节点,\(i\) 的左儿子编号为 \(2 \times i\),右儿子编号为 \(2 \times i + 1\)。用程序写出来就是:
int ls(int x) {
return x << 1;
}
int rs(int x) {
return x << 1 | 1;
}
这时候就有小朋友会问了,为什么这里会用到左移和或呢?
左移操作就是在二进制最后在加上一个 \(0\),那每一个 \(1\) 都往前了一位,所以每个 \(1\) 代表的十进制数,就变成了原来的 \(2\) 倍。
因为左移完了之后最后一位必定为 \(0\),将 \(0\) 或上 \(1\),得到 \(1\),这样我们就把最末尾的 \(0\) 改成了 \(1\),所以就加上了 \(1\)。
所以 \(x << 1 = 2 \times x,x << 1 | 1 = 2 \times x + 1\)。
因为二叉树的节点个数接近于 \(4n\),所以线段树
要开四倍空间!
要开四倍空间!!
要开四倍空间!!!
某位曹姓巨佬就因为没开四倍空间而挂掉。
为了方便,在下文的讲解和代码中,会采用以下名称:
- \(t\) 数组,即线段树数组;
- \(a\) 数组,即初始数组;
- \(tag\) 数组,即存储 \(\text{tag}\) 的数组;
- \(n\),即初始数组的大小;
- \(x\),当前遍历到的节点编号;
- \(l\),当前遍历到的区间左端点;
- \(r\),当前遍历到的区间右端点;
- \(mid\),当前遍历到的区间中点;
- \(ul\),要修改的区间左端点;
- \(ur\),要修改的区间右端点;
- \(x\),要修改区间要加上的值;
- \(ql\),要查找的区间左端点;
- \(qr\),要查找的区间右端点。
接下来,我们就一个一个的来看线段树里面的函数吧!
\(\text{PushUp}\)
不多说,最简单也是最短的一个函数。
因为非叶子节点的和就是它的两个子节点的和,所以我们要把子节点的和上传到父亲节点。
代码:
void PushUp(int x) {
t[x] = t[ls(x)] + r[rs(x)];
}
\(\text{Build}\)
从名字可以看出,就是建树,但是在建的过程中,还要将 \(\text{tag}\) 初始化一下。至于 \(\text{tag}\) 是什么,等我们讲到 \(\text{AddTag}\) 的时候再说。
我们来看建树的具体步骤:
- 初始化 \(\text{tag}\) 为 \(0\);
- 如果当前节点只有一个数,那么直接更新;
- 继续遍历左右儿子;
- \(\text{PushDown}\) 更新 \(t_x\)。
代码:
void Build(LL x, LL l, LL r) {
tag[x] = 0;
if (l == r) {
t[x] = a[l];
return;
}
LL mid = (l + r) >> 1;
Build(ls(x), l, mid), Build(rs(x), mid + 1, r);
PushUp(x);
}
\(\text{ex_Update}\)
看到标题,就有小朋友会问了:“啊你这普通 \(\text{Update}\) 还没讲就来讲加强版干什么啊?”
我只想说,这里的 \(\text{ex}\) 不是指的加强,而是:恶心!
你想,你不用线段树暴力求解,你的 \(\text{Update}\) 的复杂度是 \(O(r-l+1)\) 也就是 \(O(n)\)。
但是你用这个 \(\text{ex_Update}\) 来修改的话,复杂度是 \(O(n \log n)\),还不如暴力。
接下来,我们就来学习一下这个没用的 \(\text{ex_Update}\)
遍历到 \(x\) 这个区间时,有 \(2\) 种情况。
- 要修改的区间完全不在当前区间里,即
l > ur || r < ul
,如果是这样直接跳过。 - 否则将这个区间加上它与要修改的区间重合部分乘要修改的值。
代码:
因为这个东西过于 \(\text{ex}\),所以它被 \(\texttt{BLuemoon_}\) 删掉了。
\(\text{AddTag}\)
\(\text{tag}\) 就是解决 \(\text{ex_Update}\) 方法。
\(\text{tag}\),全名 \(\text{lazy-tag}\),懒标记。
\(\text{tag}\) 如其名,这就是为懒人准备的。
有多懒呢,你要更新一个区间,按道理你应该把这个节点的所有子节点,子节点的子节点,子节点的子节点的子节点……,全部遍历一遍,这就是 \(\text{ex_Update}\) 为什么复杂度甚至高于暴力的原因。
我们给某个点打上懒标记,并标记上此时的 \(k\) 是多少,然后把这个区间加上它应该加的就行了。
注意:这里的 \(\text{tag}\) 应该使用 +=
来更新,因为它可能原来还有没有下穿的懒标记
代码:
void AddTag(int x, int l, int r, int p) {
tag[x] += p, t[x] += p * (r - l + 1);
}
\(\text{PushDown}\)
下传懒标记。
如果这个点被标记了,那么它的所有子孙节点都应该加上对应的数,而我们只改了 \(t_x\) 的值,所以我们要不懒标记下传。步骤如下:
- 如果这个点没有懒标记,直接返回。
- 把左右儿子全部打上一样的懒标记。
- 把自己的懒标记清零。
注意:我们的 \(\text{tag}\) 存储的是 \(k\),而不是 \(k \times (r - l + 1)\),所以下传的时候不需要将原懒标记除以二,直接下传原懒标记即可。
代码:
void PushDown(LL x, LL l, LL r) {
if (tag[x]) {
LL mid = (l + r) >> 1;
AddTag(ls(x), l, mid, tag[x]), AddTag(rs(x), mid + 1, r, tag[x]);
tag[x] = 0;
}
}
\(\text{Update}\)
这次是正经的 \(\text{Update}\) 了。
步骤:
- 如果要修改区间完全包含当前区间,则直接 \(\text{AddTag}\),并返回。
- 下传标记,这里不需要判断有没有标记,\(\text{PushDown}\) 里面有判断。
- 如果左儿子和要修改区间有并集,则递归修改左儿子。
- 如果右儿子和要修改区间有并集,则递归修改右儿子。
- \(\text{PushUp}\)。
代码:
void Update(LL ul, LL ur, LL x, LL l, LL r, LL k) {
if (ul <= l && r <= ur) {
AddTag(x, l, r, k);
return;
}
PushDown(x, l, r);
LL mid = (l + r) >> 1;
if (ul <= mid) {
Update(ul, ur, ls(x), l, mid, k);
}
if (mid < ur) {
Update(ul, ur, rs(x), mid + 1, r, k);
}
PushUp(x);
}
\(\text{Query}\)
加油!这已经是最后一个函数了。如果你看完这里,那么恭喜你,已经学会线段树了!
这也是唯一一个有返回值的函数,它返回的是 \(\sum_{i=l}^{r}a_i\)。不然呢?
步骤:
- 如果要查询区间完全包含当前区间,直接返回 \(t_x\)。
- 下传懒标记,一定不要忘了这一步,因为 \(\text{Update}\) 和 \(\text{Query}\) 是混着来的,在查询的时候也可能遇到没有下传的懒标记,如果不下传,那么就这递归就会让答案变小。
- 如果左儿子和要查询区间有并集,则递归查询左儿子,当前答案加上左儿子的和。
- 如果右儿子和要查询区间有并集,则递归查询右儿子,当前答案加上右儿子的和。
- 返回答案,这里不需要 \(\text{PushUp}\)。
你自己都没有修改为什么要修改上面的
代码:
LL Query(LL ql, LL qr, LL x, LL l, LL r) {
if (ql <= l && r <= qr) {
return t[x];
}
PushDown(x, l, r);
LL mid = (l + r) >> 1, ans = 0;
if (ql <= mid) {
ans += Query(ql, qr, ls(x), l, mid);
}
if (mid < qr) {
ans += Query(ql, qr, rs(x), mid + 1, r);
}
return ans;
}
P3372完整代码
// J2023 | BLuemoon_
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int kMaxN = 1e5 + 5;
LL ls(LL x) {
return x << 1;
}
LL rs(LL x) {
return x << 1 | 1;
}
struct SegmentTree {
LL n, a[kMaxN << 2], t[kMaxN << 2], tag[kMaxN << 2];
void PushUp(LL x) {
t[x] = t[ls(x)] + t[rs(x)];
}
void Build(LL x, LL l, LL r) {
tag[x] = 0;
if (l == r) {
t[x] = a[l];
return;
}
LL mid = (l + r) >> 1;
Build(ls(x), l, mid), Build(rs(x), mid + 1, r);
PushUp(x);
}
void AddTag(int x, int l, int r, int p) {
tag[x] += p, t[x] += p * (r - l + 1);
}
void PushDown(LL x, LL l, LL r) {
if (tag[x]) {
LL mid = (l + r) >> 1;
AddTag(ls(x), l, mid, tag[x]), AddTag(rs(x), mid + 1, r, tag[x]);
tag[x] = 0;
}
}
void Update(LL ul, LL ur, LL x, LL l, LL r, LL k) {
if (ul <= l && r <= ur) {
AddTag(x, l, r, k);
return;
}
PushDown(x, l, r);
LL mid = (l + r) >> 1;
if (ul <= mid) {
Update(ul, ur, ls(x), l, mid, k);
}
if (mid < ur) {
Update(ul, ur, rs(x), mid + 1, r, k);
}
PushUp(x);
}
LL Query(LL ql, LL qr, LL x, LL l, LL r) {
if (ql <= l && r <= qr) {
return t[x];
}
PushDown(x, l, r);
LL mid = (l + r) >> 1, ans = 0;
if (ql <= mid) {
ans += Query(ql, qr, ls(x), l, mid);
}
if (mid < qr) {
ans += Query(ql, qr, rs(x), mid + 1, r);
}
return ans;
}
};
SegmentTree tr;
LL m, op, x, y, k;
int main() {
cin >> tr.n >> m;
for (LL i = 1; i <= tr.n; i++) {
cin >> tr.a[i];
}
tr.Build(1, 1, tr.n);
for (; m; m--) {
cin >> op;
if (op == 1) {
cin >> x >> y >> k;
tr.Update(x, y, 1, 1, tr.n, k);
} else {
cin >> x >> y;
cout << tr.Query(x, y, 1, 1, tr.n) << '\n';
}
}
return 0;
}
线段树板子封装结构体:
struct SegmentTree {
LL n, a[kMaxN << 2], t[kMaxN << 2], tag[kMaxN << 2];
void PushUp(LL x) {
t[x] = t[ls(x)] + t[rs(x)];
}
void Build(LL x, LL l, LL r) {
tag[x] = 0;
if (l == r) {
t[x] = a[l];
return;
}
LL mid = (l + r) >> 1;
Build(ls(x), l, mid), Build(rs(x), mid + 1, r);
PushUp(x);
}
void AddTag(int x, int l, int r, int p) {
tag[x] += p, t[x] += p * (r - l + 1);
}
void PushDown(LL x, LL l, LL r) {
if (tag[x]) {
LL mid = (l + r) >> 1;
AddTag(ls(x), l, mid, tag[x]), AddTag(rs(x), mid + 1, r, tag[x]);
tag[x] = 0;
}
}
void Update(LL ul, LL ur, LL x, LL l, LL r, LL k) {
if (ul <= l && r <= ur) {
AddTag(x, l, r, k);
return;
}
PushDown(x, l, r);
LL mid = (l + r) >> 1;
if (ul <= mid) {
Update(ul, ur, ls(x), l, mid, k);
}
if (mid < ur) {
Update(ul, ur, rs(x), mid + 1, r, k);
}
PushUp(x);
}
LL Query(LL ql, LL qr, LL x, LL l, LL r) {
if (ql <= l && r <= qr) {
return t[x];
}
PushDown(x, l, r);
LL mid = (l + r) >> 1, ans = 0;
if (ql <= mid) {
ans += Query(ql, qr, ls(x), l, mid);
}
if (mid < qr) {
ans += Query(ql, qr, rs(x), mid + 1, r);
}
return ans;
}
};
这样,你就学会了普通线段树的全部内容了,当然还有主席树,动态开点线段树,线段树合并,线段树分裂,李超线段树等等等等等等等等等等等等等……
当然,这些变种作者也不会
但是——
至少,你可以 AC
一道黄题了;至少,你可以在树状数组 TLE
的时候从容的写出一个线段树了;至少,你学会了一个 CCF \(5\) 级考点了;至少,你可以像某曹姓巨佬一样,只要看到数列就想到线段树了。
恭喜你,学会了线段树!
这就是本文的全部内容了,请帮我点一个赞然后关注我吗\(QwQ\)。
这篇文章的 Markdown
有428行,总字符数可以在标题下面看到,文件一共 \(12.2\) KB,看在我码了这么多字的份上,你真的不点一个赞吗?