Woodstock Blog

a tech blog for general algorithmic interview questions

[Fundamental] Segment Tree


Segment tree is a tree data structure for storing intervals, or segments.

Can be used to search the max/min or sum values in a range.

  1. modify = O(log n)

  2. query = O(log n)

  3. build = O(n)

question list

  1. [LintCode] Segment Tree Build

  2. [LintCode] Segment Tree Build II

  3. [LintCode] Segment Tree Modify

  4. [LintCode] Segment Tree Query

  5. [LintCode] Segment Tree Query II