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

results matching ""

    No results matching ""