Discussion @ 1613. For Fans of Statistics @ Timus Online Judge

Segment tree. Mahilewets 23 May 2017 11:15

Store a sorted array [L...R] in each vertex of your ST, corresponding to [L;R].

Re: Segment tree. Amil Khare 2 Nov 2017 22:55

Hey!
Do you mind explaining the Segment tree approach a little bit more? I still couldn't understand

Re: Segment tree. Mahilewets Nikita 3 Nov 2017 00:34

Hi
It is frequently called merge sort tree

Re: Segment tree. Mahilewets Nikita 3 Nov 2017 00:39

So there is an array TRANSPORTED[i]
If we have want to find some value in interval of array cells from i=l to i=r
We can do binary search in sorted sequence TRANSPORTED[l], TRANSPORTED[l+1],... TRANSPORTED [r-1], TRANSPORTED[r]

Re: Segment tree. Mahilewets Nikita 3 Nov 2017 00:42

In merge sort tree
We have some sorted subsequences precalculated
It is possible to represent any subsequence [l..r] as union of O(log(n)) such precalculated subsequences

Discussion of Problem 1613. For Fans of Statistics