本文主要是介绍线段树——维基百科，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
线段树[编辑]
线段树是一种二叉树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
对于线段树中的每一个非叶子节点[a,b]，它的左子树表示的区间为[a,(a+b)/2]，右子树表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树。叶节点数目为N，即整个线段区间的长度。
目录
[隐藏]- 1基本操作
- 1.1节点数据向上更新
- 1.2节点懒惰标记下推
- 1.3建树
- 1.4更新
- 1.5区间查询
- 2变种
- 3相关链接
- 4参考资料
基本操作[编辑]
给定整个线段区间，建立一棵线段树的时间复杂度是 
代码中, rt指的是root, 当前子树的根节点; l, r指的是当前子树所统计的区间![[l, r]](https://wikimedia.org/api/rest_v1/media/math/render/svg/be45874f852a2b7bfa2df52888aaec6919238623)
节点数据向上更新[编辑]
将子节点的值更新到父节点。
/* 对于区间求和 */
void push_up(int rt) {tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}/* 对于区间求最大值 */
void push_up(int rt) {tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}
节点懒惰标记下推[编辑]
对于区间求和, 原子数组值需要加上lazy标记乘以子树所统计的区间长度。 len为父节点统计的区间长度, 则len - (len >> 1)为左子树区间长度, len >> 1为右子树区间长度。
void push_down(int rt, int len) {tree[rt << 1] += lazy[rt] * (len - (len >> 1));lazy[rt << 1] += lazy[rt];tree[rt << 1 | 1] += lazy[rt] * (len >> 1);lazy[rt << 1 | 1] += lazy[rt];lazy[rt] = 0;
}
对于区间求最大值, 子树的值不需要乘以长度, 所以不需要传递参数len。
void push_down(int rt) {tree[rt << 1] += lazy[rt];lazy[rt << 1] += lazy[rt];tree[rt << 1 | 1] += lazy[rt];lazy[rt << 1 | 1] += lazy[rt];lazy[rt] = 0;
}
建树[编辑]
新建一棵长度N的线段树。
#define lchild rt << 1, l, m
#define rchild rt << 1 | 1, m + 1, r
void build(int rt = 1, int l = 1, int r = N) {if (l == r) { std::cin >> tree[rt]; return; }int m = (l + r) >> 1;build(lchild); build(rchild);push_up(rt);
}
更新[编辑]
单点更新, 不需要用到lazy标记
#define lchild rt << 1, l, m
#define rchild rt << 1 | 1, m + 1, r
void update(int p, int delta, int rt = 1, int l = 1, int r = N) {if (l == r) {tree[rt] += delta;return;}int m = (l + r) >> 1;if (p <= m) update(p, delta, lchild);else update(p, delta, rchild);push_up(rt);
}
成段更新, 需要用到lazy标记来提高时间效率
#define lchild rt << 1, l, m
#define rchild rt << 1 | 1, m + 1, r
void update(int L, int R, int delta, int rt = 1, int l = 1, int r = N) {if (L <= l && r <= R) {tree[rt] += delta * (r - l + 1);lazy[rt] += delta;return;}if (lazy[rt]) push_down(rt, r - l + 1);int m = (l + r) >> 1;if (L <= m) update(L, R, delta, lchild);if (R > m) update(L, R, delta, rchild);push_up(rt);
}
区间查询[编辑]
#define lchild rt << 1, l, m
#define rchild rt << 1 | 1, m + 1, r
int query(int L, int R, int rt = 1, int l = 1, int r = N) {if (L <= l && r <= R) return tree[rt];if (lazy[rt]) push_down(rt, r - l + 1);int m = (l + r) >> 1, ret = 0;if (L <= m) ret += query(L, R, lchild);if (R > m) ret += query(L, R, rchild);return ret;
}
变种[编辑]
zkw线段树是一种自底向上的线段树，由清华大学的张昆玮提出。它相对于传统线段树的优势体现在减少了递归操作和增加了位运算等操作以减少常数[1]。
相关链接[编辑]
http://dongxicheng.org/structure/segment-tree/
参考资料[编辑]
- ^ 张昆玮. 统计的力量——线段树全接触.
这篇关于线段树——维基百科的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
