Thursday, January 19, 2017

Episode 4 - Segment Trees

By popular request, this week's episode will cover segment trees. This data structure is a bit of a strange one. When I first learned them, the structure was referred to as an interval tree. Academic literature has a very different data structure called interval tree. Later on, I heard the data structure referred to as segment tree, but once again theoretical computer science has a different data structure called segment tree. The Croatian Open Competition in Informatics (COCI) refers to them as a tournament tree, but this name is also a bit misleading. Despite the confusion on the name, this data structure technique is extremely useful and flexible in competitive programming.

I recommend reviewing the merge sort algorithm before viewing this episode as the structure of segment tree closely mirrors the structure of merge sort's recursion. I'll be thorough in both the theoretical and implementation basics of this wonderful data structure.

See you live! (time, stream, channel)

No comments:

Post a Comment