定義
セグメントツリーの概念を紹介します。 便宜上、配列の長さに2のべき乗を加えます。 配列に追加された要素に無限大を追加します（無限大の場合、たとえば、データに何も表示されない数を理解することは価値があります）。 したがって、セグメントのツリーは二分木であり、各頂点には特定の関数の値が特定のセグメントに書き込まれます。 私たちの場合の機能は最小限です。
各シートには、ツリー内のシートの序数に等しい数の配列要素があります。 そして、葉ではない各頂点は、この頂点の子孫シートに対応する配列要素のセグメントに対応します。
定義の明らかな怪物の背後には、完全に単純な概念があります-私たちは図に目を向けます。
定義を説明しましょう。 選択された頂点は、指定された頂点のすべての子孫シートの結合であるため、マークされたセグメントに対応します（この瞬間から、シートとそれが表す配列要素を識別します）。
ツリーをバイナリヒープのように保存します。 配列T [2n-1]を取得します。 ルートは配列の最初の要素にあり、i番目の頂点の息子はそれぞれ番号2iと2i + 1-左と右の要素にあります。 葉ではないi番目の頂点に対して、T [i] = min（T [2i]、T [2i + 1]）という明らかなプロパティがすぐにわかります。 ところで、シートは、nから2n-1までの数字を持つ要素にこのような番号を付けます。
建物
（n-1）番目から最初まで要素を調べて、各頂点の息子の最小値をカウントすることでツリーを構築します。
この記事から始めて、より明確にするためにコードを提供します。
const int INF = INT_MAX; void build_tree(const vector<int>& V) { // , int n = (1 << (log(n - 1) + 1)); V.resize(2 * n, INF); // for (int i = n; i < 2 * n; i++) V[i] = V[i - n]; // for (int i = n - 1; i > 0; i--) V[i] = min(V[2 * i], V[2 * i + 1]); }
build_tree（V）関数は、配列Vをこの配列の行ツリーに変換します。 それでは、セグメント上の最小値をどのように見つけるのでしょうか？ これを行うために、基本的なセグメントの概念を紹介します。
最小要求
配列の基本セグメントを、対応するツリーに頂点があるセグメントと呼びます。 セグメントを最小数の互いに素な基本セグメントに分割します。 各レベルでその数が2を超えないことを示します。
パーティション内の最大の基本セグメントを取得します。 その長さを2トンにします。 長さ2tの基本セグメントは最大2つであることに注意してください。 利用可能な左端の最大基本周波数を取得します。 それから左に移動します。 繰り返しますが、セグメントの長さが短くなることに注意してください（2）。 したがって、最大値の権利があります。 したがって、基本セグメントは最大2tであり、2lognを超えないことがわかります。 証拠のパラグラフ（1）および（2）は、自己反省のために残します。
これはどのように役立ちますか？ これで、最小限のリクエストを下から実装できます。 必要に応じて各レベルでの基本的なセグメントを追加して、下から上昇します。
パーティションの次の基本セグメントを見つけるために、lとrの2つのポインターを取得します。 最初に、クエリセグメントの両端に対応するシートを指すようにlとrを設定します。 lがその親の右息子である頂点を指す場合、この頂点は基本セグメントへのパーティションに属し、そうでない場合はそうではないことに注意してください。 同様に、ポインターrで、親の左息子である頂点を指す場合、パーティションに追加します。 その後、両方のポインターをより高いレベルに移動し、操作を繰り返します。 ポインタが次々と来るまで操作を続けます。
次の基本セグメントを見つけて、その最小値を現在の最小値と比較し、必要に応じて減らします。 アルゴリズムの漸近的な動作はO（logn）です。これは、各レベルで一定数の操作を実行し、合計レベルがlognであるためです。
int rmq_up(vector<int>& T, int l, int r) { int ans = INF; int n = T.size() / 2; l += n - 1, r += n - 1; while (l <= r) { // l - , // if (l & 1) ans = min(ans, T[l]); // r - , // if (!(r & 1)) ans = min(ans, T[r]); // l = (l + 1) / 2, r = (r - 1) / 2; } return ans; }
修正
次に、ツリー要素の値を変更する方法を学びます。 各葉には、それを含む基本セグメントのログが正確にあることに注意してください。それらはすべて、葉から根までのパス上にある頂点に対応しています。
したがって、要素を変更するときは、単純にそのリーフからルートに移動し、式T [i] = min（T [2i]、T [2i + 1]）に従ってパス上のすべての頂点の値を更新するだけで十分です。
void update(vector<int>& T, int i, int x) { int n = T.size() / 2; i += n – 1; T[i] = x; while (i /= 2) T[i] = min(T[2 * i], T[2 * i + 1]); }
やった！ （O（n）、O（logn））で動的RMQ問題の解決策を取得します。
次の記事では、上からリクエストを行う方法を学びます。 上記からのリクエストの漸近性は同じであるという事実にもかかわらず、それは1つの大きなバンを持っています-セグメントに変更を簡単かつ簡単にねじ込む能力。 じゃあね！