エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント1件
- 注目コメント
- 新着コメント
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
セグメント木を徹底解説!0から遅延評価やモノイドまで | アルゴリズムロジック
セグメント木とは セグメント木とは、完全二分木(全ての葉の深さが等しい木)によって実装された、区間... セグメント木とは セグメント木とは、完全二分木(全ての葉の深さが等しい木)によって実装された、区間を扱うのに適したデータ構造のことです。 区間に対する操作を対数時間 O(log n) で行えることが特徴で、競技プログラミングなどで頻出となっています。 セグメント木でできること セグメント木は、区間に対する操作やクエリを行うことができます。 特に、 区間上の値を更新する任意の区間上の最小値や合計値などを取得する などが対数時間でそれぞれ行えるのが強みです。 区間上の合計値などは、累積和などを使えば前処理 O(N) ・クエリ O(1) で取得することもできます。しかし、区間上の値の更新と、合計値の取得が入り乱れるような時は、セグメント木の方が有効になることが多いです。 以下では説明のために、区間上の最小値 Range Minimam Query(RMQ) を扱うセグメント木を例として説明します
2020/03/13 リンク