Basics
基本定义
- 线段树,also 区间树 (interval tree),它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题 (比如某些数据可以按区间进行划分,按区间动态进行修改,而且还需要按区间多次进行查询,那么使用线段树可以达到较快查询速度)。线段树的每个节点表示一个区间,子节点则分别表示父节点的左右半区间,例如父亲的区间是[a,b],那么(c=(a+b)/2)左儿子的区间是[a,c],右儿子的区间是[c+1,b]。(http://www.cnblogs.com/TenosDoIt/p/3453089.htm
- support queries like:
- which of these intervals contain a given point
- which of these points are in a given interval e.g. 给你个范围(index 1~10) 返回最大值
基本操作
- build: o(n)
- update: o(logn)
- query: o(logn)
- 因为优化了 update and query (tradeoff: need rebuild tree), 最适合用 Segment tree 的情形最好**同时**满足以下三点
- 区间查找 min/max
- 频繁 update
- 频繁 query
Tips
- Segment Tree 是一个 Perfect Binary Tree. Each node has 0 or 2 children, balanced tree. (满的 平衡的)
- 给定含 n 个元素的数组区间,由于最后的 leaf node = [a, a] 所以
- 对应的 Segmeng Tree 节点数量为 2n - 1. (e.g. n = 5, then nodes <= 9)
- 深度 log(n) + 1
- 偶数长度区间会拆出 两个偶数 or 两个奇数长度区间,最终以长度为 1 的区间为叶节点
- 奇数长度区间会拆出 一个偶数 + 一个奇数长度区间,最终以长度为 1 的区间为叶节点
- partial overlap - search both branch
- total overlap - return node value
- no overlap - return max / min
- lazy propagation
Problems
Segment Tree Build: http://www.lintcode.com/en/problem/segment-tree-build/#
Segment Tree Build ii: http://www.lintcode.com/en/problem/segment-tree-build-ii/
Segment Tree Modify: http://www.lintcode.com/en/problem/segment-tree-modify/
Segment Tree Query: http://www.lintcode.com/en/problem/segment-tree-query/#
Segment Tree Query ii: http://www.lintcode.com/en/problem/segment-tree-query-ii/#
Range Sum Query - Mutable: https://leetcode.com/problems/range-sum-query-mutable/#/description
- Fenwick Tree (Binary Indexed Tree)
Range Sum Query - Immutable: https://leetcode.com/problems/range-sum-query-immutable/#/description
Range Sum Query 2D - Mutable: https://leetcode.com/problems/range-sum-query-2d-mutable/#/description
Range Sum Query 2D - Immutable: https://leetcode.com/problems/range-sum-query-2d-immutable/#/description