Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### Misa-Misa's blog

By Misa-Misa, history, 6 months ago,

we have a permutation p of size N.

we iterate on this permutation and insert elements into a Binary Search Tree.

Prove that each sub-tree will consists of all elements from some l to r.

In other words, prove that elements of each sub-tree form continuous subarray of identity permutation (if written is sorted order).

identity permutation -> 1, 2, 3, 4 ... N.

• +4

 » 6 months ago, # |   0 Auto comment: topic has been updated by Misa-Misa (previous revision, new revision, compare).
 » 6 months ago, # |   +18 Proof by induction.Base case: $n \le 1$. Trivial.Induction: Let us assume that we inserted $k$ first from the permutation of length $n$. Then, all elements smaller than $k$ will be on the left subtree, and the rest are on the right subtree. Then the left subtree is a permutation of $[1,k-1]$, and the right subtree is a permutation of $[k+1,n]$. A permutation of $[1,k-1]$ is a permutation of length $k-1$, and a permutation of $[k+1,n]$ is similarly a permutation of length $n-k$. Thus the induction holds.
•  » » 6 months ago, # ^ |   +3 Got it. Thanks.