クマーの競プロ精進日記

AtCoder赤とICPC World Final目指して頑張ります．競プロ自戦記、アルゴリズムなどについて

Cartesian tree の性質

列 a_0, \dots, a_{N-1} についての最小値を根とする Cartesian tree についての性質

  • 0\le i\lt j\lt N について，頂点 i と j の一方がもう一方の先祖である \displaystyle \iff \min\lbrace{a_i, a_j\rbrace} = \min_{i\le k\le j} a_k
    • 特に， i と i+1 は必ず先祖と子孫の関係にある
    • クイックソートの期待計算量の解析にもこの性質が利用できる