Tutorial by Examples

Suppose we have an array: +-------+-----+-----+-----+-----+-----+-----+ | Index | 0 | 1 | 2 | 3 | 4 | 5 | +-------+-----+-----+-----+-----+-----+-----+ | Value | -1 | 3 | 4 | 0 | 2 | 1 | +-------+-----+-----+-----+-----+-----+-----+ We want to perform some query on thi...

Let's say, we have an array: Item = {-1, 0, 3, 6}. We want to construct SegmentTree array to find out the minimum value in a given range. Our segment tree will look like: The numbers below the nodes show the indices of each values that we'll store in our SegmentTree array. We can see that, to sto...

The procedure to perform a RMQ is already shown in introduction. The pseudo-code for checking Range Minimum Query will be: Procedure RangeMinimumQuery(SegmentTree, qLow, qHigh, low, high, position): if qLow <= low and qHigh >= high //Total Overlap Return SegmentTree[position] el...

Let's say, you have already created a segment tree. You are required to update the values of the array, this will not only change the leaf nodes of your segment tree, but also the minimum/maximum in some nodes. Let's look at this with an example: This is our minimum segment tree of 8 elements. To...