Segment Tree

Used when we need to find

  • max/min
  • sum
  • product

of numbers in a range

线段树并不适合所有区间查询情况，它的使用条件是“相邻的区间的信息可以被合并成两个 区间的并区间的信息”。即问题是可以被分解解决的

idea

We have an array arr[0....n-1]

  1. find the sum of elements from index l ro r
  2. change the value of a specified element of the array arr[i]

Use normal query 1 would take O(1)

Another solution is to create another array and store the sum from start to i at the ith index in the array. but update takes O(n).

Segment Tree

Using segment tree, both update and query sum can take O(logn) time.

  1. leaf nodes are the elements of the array.
  2. each internal node represents some merging of the left nodes. The merging may be different for different problems.

segment tree

An array representation of tree is used to represent Segment Trees. For each node at index i, the left child is at index 2i+1, right child at 2i+2

Operation

  • build O(n)

Build是一个recursive的过程，不断地将区间分成两半。

root节点表示区间[0, N-1], 然后不断减半，不难证明，这样的segment tree的节点数 只有2N-1个，是O(N)级别的。

  • query O(logn)

  • Range update O(logn)

References