线段树
2021/9/28 6:12:31
本文主要是介绍线段树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
线段树
1.线段树的建树
build函数:
build(u, l, r):u表示当前节点编号,l、r分别是该节点所代表区间的左右端点[l, r].
struct SegmentTree{ int l, r; int dat; }t[SIZE * 4]; void build(int u, int L, int R) { t[u].l = L, t[u].r = R; if (L == R) { t[u].dat = a[L]; return; } int mid = (L + R) >> 1; build(2*u, L, mid); build(2*u + 1, mid + 1, R); //一般来说是Pushup()操作; t[u].dat = max(t[u*2].dat, t[u*2 + 1].dat); }
2.线段树的单点修改
线段树中,根节点(编号为1)是执行的入口,需要从根节点出发,递归找到区间[x, x]的叶节点,然后对该节点
进行修改,并自底向上更新信息。时间复杂度为O(logN):树的高度;
//在节点编号为u,区间x位置处,变更为v; void change(int u, int x, int v) { if (t[u].l == t[u].r) { t[u].dat = v; return; } int mid = (t[u].l + t[u].r) >> 1; if (x <= mid) { //左子树遍历; change(2*u, x, v); } else { change(2*u + 1, x , v); } //自底向上更新信息; t[u].dat = max(t[2*u].dat, t[2*u + 1].dat); }
3.区间查询
假设我们所想要查询的区间为[L, R], 线段树所建立的区间为[TL, TR];
那么从根节点开始,递归执行如下过程:
- 如果[L, R] 包含[TL, TR],说明L<=TL && R >= TR, 那么直接返回[TL, TR]上的相关信息即可, 对于非[TL, TR]区间的不用考虑,因为一开始就建立的线段树就没考虑这段区间;
- 如果[L, R]和[TL, TR]有部分重叠, 那么可以分三种情况讨论:
对于mid = (TL + TR) / 2, 且有TL <= L <= TR <= R,
- 如果L > mid, 说明[TL, TR]的右半部分和[L, R]重叠,因此只需递归右边即可;
- 如果 L <= mid, 虽然会递归两颗子树,但是右半边的递归会和1情况类似,所以右边递归时会直接返回;
- 对于L <= TL <= R <= TR, 情况和上面是对称的;
- 如果TL <= L <= R <=TR, 即[L, R]被[TL, TR]所包含,
- 对于L,R都处于mid的左边或右边时,那么只会递归一颗子树;
- 当L, R分别在mid的左右两边时,这时才会递归两边,但需要考虑到下一层递归时,会变成2或3中部分重叠的情况
- 如果[L, R]和[TL, TR]不存在重叠,因为我们是从根节点开始,即[1, N]开始,除非一开始就是没有交集的,不然必定会回到1和2的情况,因此这种情况不必讨论;
比如查询区间[l, r]上的最大值;
int Query(int u, int l, int r) { if (t[u].l >= l && t[u].r <= r) { return t[u].dat; //完全包含关系; } int mid = (t[u].l + t[u].r) >> 1; int val = -(1<<30); //-inf; if (l <= mid) val = max(val, ask(2*u, l, r)); //左子节点有重叠; if (r > mid) val = max(val, ask(2*u + 1, l, r)); //右子节点有重叠; return val; }
参考
- 算法进阶指南;
这篇关于线段树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?