自然
デカルト ツリーは、「最小値を再帰的に使用して区間を分割する」バイナリ ツリーです。
シーケンスが与えられた場合、次のようなことを行います。
- シーケンス全体を検索する最小値として扱います根；
- 最小値左の後続は再帰的に構築されます左のサブツリー；
- 最小値右の後続は再帰的に構築されます右サブツリー。
このようにして得られた木はデカルト木です。 「間隔最小値」などの情報を利用して、ツリー構造明示的に表現された
再帰的定義
シーケンスを次のようにします \([1\dots n]\)(要素の複製を許可します)、そのデカルト ツリーを定義します。
- シーケンスが空の場合、対応する空の木；
- それ以外の場合は、 \(m\) はい \(a\) 真ん中最小値最初の出現位置
- ルートノードの対応する位置 \(m\)体重は \([m]\)；
- 左のサブツリー = \([1\dots m-1]\) デカルト木。
- 右サブツリー = \([m+1\dots n]\) デカルト木。
例：\(a = [4, 1, 3, 2, 5]\)（添字 \(1\) 到着 \(5\)）
- グローバル最小値は次のとおりです \([2]=1\)ルートは添え字です \(2\)；
- 左半分 \([4]\)（添字 \(1\)) 左側のサブツリーを構築します。
- 右半分 \([3,2,5]\) 最小値は \([4]=2\)右のサブツリーのルートとして、その左 \([3]\)、右 \([5]\) 彼らはそれぞれその左と右の息子です。
2(值=1) ← 全局最小值是根
/ \
1(值=4) 4(值=2) ← 右半段 [3,2,5] 的最小值是 2
/ \
3(值=3) 5(值=5)
再帰的な定義から、すぐに 2 つのことがわかります。重要な事実：
- インオーダートラバーサル (左-ルート-右) は元のシーケンスの順序とまったく同じです
- ルートはグローバル最小値です。各ノードの重みはサブツリー全体のすべての値以下です——まさに「小さな根っこ」の性質ですね。
二分探索木 + ヒープ
再帰的な定義は直感的ですが、次の方がより一般的に使用されます。同等の定義
デカルト ツリーの各ノードには 2 つのキーがあります。
| 鍵 | 意味 | 満足のいく性質 |
|---|---|---|
| 鍵（鍵） | 通常は配列の添字として使用されます \（私\） | 満足する二分探索木プロパティ: 左側のサブツリー内のすべてのキー < root, all keys in the right subtree > 根 |
| 価値（重さ） | 配列要素として取得 \([i]\) | 満足する小さな根の山プロパティ: ルートの値 ≤ サブツリー内のすべての値 |
今すぐ：順走査は添字の昇順であり、重みはルートから下に向けて単調に減少しません (ルート ヒープが小さい)。。
これら 2 つのプロパティと前のセクションの再帰的定義は次のとおりです。全く同等の：
- 「キーはBSTを満たしています」 \(\Longleftrightarrow\) 順序トラバーサルは添字順序です \(1,2,\ドット,n\)；
- 「値は小さなルート ヒープを満たす」 \(\Longleftrightarrow\) 各ノードは、そのサブツリー (連続区間) の最小値です。
したがって、デカルト ツリーは、「位置による順序付け」と「サイズによる階層化」を同時に行うツリーです。。
自然
プロパティ 1: 順序どおりの走査 = 元のシーケンス
特性 2: 独自性
特性 3: サブツリー = 連続区間
特性 4: ノードはそのサブツリー間隔の最小値です
特性 5: 間隔の最小値 = LCA
任意の間隔で \([l, r]\)（\(l \le r\)）、間隔の最小値の位置 = ノード \(l\) ノード付き \(r\) デカルト ツリー上の LCA (最後の共通祖先)。
この物件 RMQの質問 そして LCA 接続されると、この 2 つは相互のブリッジとして機能します。
モノトーンスタックO(n)ツリー建築
再帰定義では毎回「間隔の最小値」を求める必要があります。毎回スキャンする場合は、 \(O(n^2)\) の。しかし、私たちは使うことができます単調なスタックツリー全体を線形時間で一度に構築します。
左から右へ一人ずつ参加してください添字 \（私\）。常にスタックを維持し、スタックには “現在構築されているツリーの右リンク「――つまり、根元から右にずっと続く道です。そして、この右の鎖にかかる重みは、厳密に増加(小さなルート ヒープの要件: ルートに近づくほど、重みは小さくなります)。
新しいノードを追加する \（私\） 時間：
- スタックをポップする: スタックの一番上のウェイトを削除します。 > \([i]\) のすべてのノード \（私\） ビッグ、ここに留まるべきではない \（私\） 上記)、最後のポップアップ ノードを次のように記録します。
last； - 右側の息子を吊るす: スタックが空でない場合は、スタックの一番上が最初のウェイトであることを意味します ≤ \([i]\) ノード、させてください \（私\） そのものになる右の息子明らかに、このステップは次の条件を満たします\(MST\) 自然;
- 下がる \（私\） 左の子: ポップされたノードの全体的な比率 (そのサブツリーも含む) \（私\） 大きくなる \（私\） の左子たとえ
lastなる \（私\） 左息子、明らかにこのステップも満足です \(MST\) これらのノードは \（私\）以前にアクセスされ、接続されたばかりです。 - スタックにプッシュする: put \（私\） スタックの一番上にプッシュします (正しいチェーンを維持し続けます)。
すべての添え字が処理された後、スタックの一番下の要素はグローバル最小値であり、ルートになります。。
正しさ
鍵：各ノードはスタックを 1 回だけ「ポップ」し、「プッシュ」します。したがって、全体の複雑さは \（の上）\）。
テンプレート
P5854[Template]デカルトの木
#include
using namespace std;
using ll = long long;
const int N = 1e7 + 5;
ll n;
ll p[N];
ll ls[N], rs[N];
ll stk[N], top;
ll root;
void build() {
top = 0;
for (int i = 1; i <= n; i ++) {
ll lst = 0;
while (top && p[stk[top]] > p[i]) lst = stk[top --];
if (top) rs[stk[top]] = i;
if (lst) ls[i] = lst;
stk[++ top] = i;
}
root = stk[1];
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++) cin >> p[i];
build();
ll x = 0, y = 0;
for (int i = 1; i <= n; i ++) {
x = x ^ (i * (ls[i] + 1));
y = y ^ (i * (rs[i] + 1));
}
cout << x << ' ' << y << '\n';
return 0;
}
その他の用途
- 辞書編集的な最小限のツリー走査: 「重みによって制限され、位置によって構築される」いくつかのツリー問題は、デカルト ツリーの構造で直接処理できます。
- インターバル最大値分割DP: 「区間の最小値を毎回取って区間を2等分する」形式の分割統治型DPで、その再帰木はデカルト木であり、その木の上にツリー状のDPを作ることができます。
注記：
鎖に退化する: シーケンスが単調である場合 (厳密に増加する場合など)、デカルト ツリーは右チェーン(または左チェーン)、深さ \（の上）\）。このとき、再帰を使用する場合はスタック爆発に注意し、非再帰を使用する必要があります。
要約する
- 自然: デカルト木 = 「最小間隔」を使用してシーケンスを再帰的に分割することによって得られる木。
- 二重構造: インオーダー = 元のシーケンス順序 (BST)、重み = 小さなルート ヒープ。
- コアプロパティ：間隔 \([l,r]\) 最小値位置 = LCA\((l,r)\)。
- 建てる: 単調スタック \（の上）\）。
- 応用: 最大サブ長方形、RMQとLCAの変換、間隔最小値パーティションクラスDP。
