ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1613. For Fans of Statistics

Segment tree.
Posted by 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.
Posted by 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.
Posted by Mahilewets Nikita 3 Nov 2017 00:34
Hi
It is frequently called merge sort tree
Re: Segment tree.
Posted by 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.
Posted by 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