Segement Tree

Source: https://www.dgp.toronto.edu/public_user/JamesStewart/378notes/22intervals/

裡面的 Interval Tree 實際上是對應 Segment tree ，不曉得是不是通用稱法。下面以 Segment Tree 稱之。

名詞介紹

• interval: 由兩個整數 a, b 構成的區間[a, b]
• elementary interval: 加入 integer line 而切割出的不同區段

給定 n 個 intervals [ai, bi], for i = 1 … n, 假設這些 intervals 不共享 endpoint，那會得到 2n + 1 個 sub-intervals。

每個 interval 能以 sub-intervals 表示

****	Interval	spans Sub-Intervals
x	[10,20]	[10,15], [15,18], [18-20]
y	[15,25]	[15,18], [18,20], [20-22], [22,25]
z	[18, 22]	[18,20], [20,22]

Internal Node & Leaf Node

• internal node: 儲存 key，分離 elementary intervals 至左右子樹
• leaf node: 代表 elementary interval

用途

• 查詢給定點在哪些線段裡
• 括增 BST
• complexity
  • Build: O(n log n)
  • Query: O(log n+k), n=# of interval, k=# of result
  • Space: O(n log n)
• cannot be modified once built
• complete binary tree

  • 各層節點全滿，除了最後一層，最後一層節點全部靠左。

    

儲存 Intervals

如果於 leaf 儲存 non-elementary interval (涵蓋 elementary interval 的 interval)，最糟情況下所有 interval 非常長，所有 leaf 儲存所有 elementary interval，因為有 n 個 leaf，儲存開銷是 O(n^2)。

Segment tree 如何改善儲存開銷？internal node 用 sub-tree 來 span elementary interval 的聯集。

# For example, node 18 spans the interval from 15 to 20
span(18) = [15,20]

把 interval 儲存在 internal node 而不是 leaf 上

An interval [a,b] is stored in a node x if and only if

1. span(x) is completely contained within [a,b]
2. span(parent(x)) is not completely contained in [a,b]

還能得到兩點

1. interval 只會出現最多兩次在同一 level
2. 儲存空間 O(n log n)，實際上是 2 n log n (稍候證明)

Example

Interval	Composer	Birth	Death
A	Stravinsky	1888	1971
B	Schoenberg	1874	1951
C	Grieg	1843	1907
D	Schubert	1779	1828
E	Mozart	1756	1791
F	Schuetz	1585	1672

ex1

Grieg’s lifetime = [1843,1907] 儲存在 node 1888，因為

1. span(1888) = [1874,1907] is completely contained within [1843,1907] and
2. span(parent(1888)) = [1874,1951] is not completely contained within [1843,1907].

ex2

• 尋找包含 G = [1672,1779] 的 nodes
  1. 將 G 帶入 [1672,1779] 所 span 的 elementary node
  2. 檢查 (1), (2) 直到 G 無法再往 parent 移動

ex3

proof: Given this information and the fact that a tree of n  intervals has O(n) leaf nodes, what is an asymptotic upper bound on the space required to store the n intervals inside the tree nodes? Assume that an interval requires O(1) space for each node in which it is stored.

查詢 Intervals

給定 integer k 和 interval tree T，列出所有 T 內包含 k 的 interval。

An interval [a,b] contains k if a <= k <= b.

作法如下

1. 在所有的 leaf (elementary interval) 尋找包含 k 的 interval
2. 在所有的 interval node 尋找包含 k 的 interval

總結就是以 root-to-leaf 的方式找尋

• 包含 k 的 interval 和 leaf (elementary interval)

用下述作法找出的 interval 為 [a, b)

listIntervals( k, x )

  while x != NULL
    output intervals(x)
    if k < separator(x)
      x = left(x)
    else
      x = right(x)
    endif
  endwhile

插入 Interval

在 internal tree 中插入 interval [a,b]，假設 a, b 已在樹內。

1. 從上到下找尋 node 所 span 的範圍在 [a, b] 內
2. (rule 2 已經滿足，否則不會接觸到該 node)

inrerval 有可能儲存在不同子樹的線段內，因此左右子樹都要尋找

以 binary search 的方式往下尋找，符合 rule 1 就插入該 node 或是碰到 leaf 停止。

/* addInterval( I, a, b, min, max, x )
 *
 * The interval to insert is [a,b] and is named I.  We assume that the
 * values a and b separate elementary intervals somewhere in the tree.
 * [min,max] is the span of the current subtree rooted at node x.
 *
 * This is initially called as addInterval( I, a, b, -infinity, +infinity, root ).
 */

addInterval( I, a, b, min, max, x )

  if a <= min and max <= b

    /* span(x) is completely within [a,b], so store the interval and stop */

    store I in intervals(x)

  else

    /* span(x) contains some elementary intervals that aren't in [a,b].
     * We must recurse until we find a subtree that is completely contained
     * in [a,b].  Note that we might recurse into both subtrees. */

    if (a < separator(x))
      addInterval( I, a, b, min, separator(x), left(x) );
    endif

    if (separator(x) < b)
      addInterval( I, a, b, separator(x), max, right(x) );
    endif

  endif