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...
This implementation accepts a generic binary operator, such as max, min, add, multiply, etc.:
https://bitbucket.org/StableSort/play...
Source code of FenwickTree implementation written in Java:
https://bitbucket.org/StableSort/play...
Also see Fenwick Tree tutorial:
• Fenwick Tree (Binary Index Tree) - Qu...
Wikipedia:
https://en.wikipedia.org/wiki/Segment...
Written and narrated by Andre Violentyev
На этой странице сайта вы можете посмотреть видео онлайн Segment Tree Data Structure - Min Max Queries - Java source code длительностью часов минут секунд в хорошем качестве, которое загрузил пользователь Stable Sort 02 Февраль 2020, поделитесь ссылкой с друзьями и знакомыми, на youtube это видео уже посмотрели 25,794 раз и оно понравилось 1 тысяч зрителям. Приятного просмотра!
![[科普]如果全世界的貓突然死掉會發生甚麼事情 What If All Cats Died Right Now](https://image.4k-video.ru/id-video/tkApspy6jgo)
