Interval Trees and Segment Trees

Interval trees and segment trees are two popular but not-so-popular data structure and they may be asked during job interview. The key difference between interval trees and segments is the first one faces intervals while the second one deals with points.

  • Interval Tree: Reference from G4G. Note that we assume that all the intervals do NOT overlap. This is a very strong assumption and I don't like that.

  • Segment Tree: Reference from G4G