Segment Tree Data Structure - Min Max Queries - Java source code смотреть онлайн

In this tutorial we’ll talk about a data structure called Segment Tree. We’ll go over what it’s for, when to use it, and then we’ll step through the source code of a particularly efficient implementation, both in terms of running time and the amount of space that it requires, written in Java. It uses an array that's exactly twice the size of the original input array. Thus, no space is being wasted, even if the size of the input array is not in the power of 2.

Segment Tree is a data structure that facilitates fast range queries, such as finding the sum across a range of numbers. If you have seen our previous episode on Fenwick trees, you can think of it as a bigger, fatter cousin to Fenwick Tree. It takes up more storage space, but, along with summation, multiplication, and XOR operations, it also can find MIN and MAX or any other binary associative operation.

The Segment Tree pre-computes the max/min for only a specific set of ranges, but it’s done in such a way that you could still find the max over any range in O(log n) running time.

Source code of Segment Tree implementation written in Java:
https://bitbucket.org/StableSort/play/src/master/src/com/stablesort/segtree/SegmentTreeMax.java

This implementation accepts a generic binary operator, such as max, min, add, multiply, etc.:
https://bitbucket.org/StableSort/play/src/master/src/com/stablesort/segtree/SegmentTree.java

Source code of FenwickTree implementation written in Java:
https://bitbucket.org/StableSort/play/src/master/src/com/stablesort/fenwick/FenwickTree.java

Also see Fenwick Tree tutorial:
https://youtu.be/uSFzHCZ4E-8

Wikipedia:
https://en.wikipedia.org/wiki/Segment_tree

Written and narrated by Andre Violentyev