how to

笛卡尔树上 LCA 为区间最值的说明

Aug 28, 2024
langsalgo
1 Minutes
190 Words

笛卡尔树上 LCA 为区间最值的说明

若 x, y 的 LCA 为 a,则 a 为 x ~ y 的区间最小值。

  • 每个结点的左延伸和右延伸是它作为最小值的极限范围
    • 因为左链再左边一个元素是你的某个祖先,而你的祖先都比你小
    • 而且你的子树中你是最小的
  • 设 a 为 x, y 的 LCA。则必有其中一个在 a 左子树中(设为 x),y 在 a 右子树中
    • 故 x 在 a 左边,y 在 a 右边
    • 而且 x, y 在 a 作为最小值的范围内
  • 补充:考虑 a 的父亲 f,由于 a 是 f 的子树故 x 和 y 都在 f 的同一边。故 f 不是在 x ~ y 区间内
Article title:笛卡尔树上 LCA 为区间最值的说明
Article author:Julyfun
Release time:Aug 28, 2024
Copyright 2025
Sitemap