beet's soil

競プロのことなど

競技プログラマのための抽象セグメント木実装のすすめ

午前起床！（素振り）

はじめに

先にこっちを見て　
beet-aizu.hatenablog.com

うし木（一点更新区間取得）について書きます

おまけ

なんだこれはたまげたなあ（わかる人にはわかる記事、わからない人にはわからない）
beet-aizu.hatenablog.com

前提知識(C++)

厳密性や歴史的背景をガン無視しています。あんまりあてにしないでください。
雰囲気を掴むためと割り切って読んでもらえるといいと思います。
C++のバージョンは14を前提にしていますがそのうち17に上がりそう？

struct is 何

競技プログラマならpairやtupleくらいは使ったことがあると思いますが、自分でそういうのを作るための機能です。
たとえば

struct Node{
  int fi,se;
};
Node v;
v.fi=0;v.se=1;

みたいな感じで使えます。
つまり、大きなまとまりを作って、その中の変数をひとくくりに扱うことができます。

template is 何

先ほどの例では型がint固定でしたが、これはかなり不便です。
templateを使うことで、1つの宣言で複数の型に対応できます。
実際、pairは

template<typename T, typename U>
struct pair{
  T first;
  U second;
  pair(T x,U y):first(x),second(y){}
};

みたいな感じで実装されてるはずです。（知らんけど）

ラムダ式 is 何

関数を変数として扱うための構文です（本当か？）

[&](int a,int b)->int{return a+b;};

みたいに書きます。
[&]の部分で外部の変数を参照できるようになります。
その次の()の部分は普通の関数と同じように引数を並べます
その次の->の部分は返り値の型を指定します　コンパイラが推論できる場合は省略可能です
たとえば

[&](int a){if(a==0) return 1;return 0.5;};

みたいなやつは返り値の型の候補が複数あって推論できないのでCEになります。
続く{}の中は普通の関数と同じようにかけばいいです。

変数に保存したい場合は

auto f=[&](int a,int b){return a+b;};

のようにかけばいいです。
ラムダ式は型が特殊なので、autoで受け取るのが楽です。

呼び出しは普通の関数と同じようにできます。

f(2,3);

は、5を返します。

実装するべき関数群

init

サイズを2べきにしたりする関数

build

vectorを受け取って初期化をO(N)でやる関数
最悪なくてもset_valをN回呼べばいいけどオーダーが悪くなる

set_val

一点を更新する関数

query

区間の取得をする関数

細かい話いろいろ

うし木に限ってしまえば、update（一点加算とか）は作らない方が綺麗だと思います。
うし木はモノイドを管理するデータ構造であって、作用付きモノイドを管理するデータ構造ではないので。

単位元と初期値が異なる問題も結構あります。
どちらにせよvector(size,初期値)をbuildに渡せばいいです。

ほんへ

抽象セグ木の書き方を紹介していきます

グローバルに関数ベタ書き
  • 自由度が高い
  • C++の前提知識が不要
  • 複数本持つのがたいへん
using T = int; // 直す
T identity = 0; // 直す
T merge(T x,T y){} // 書く

const int MAX = 1<<17;
T dat[MAX];

// initとかqueryとか set_valとか
structにする
  • （コピペすれば）複数本持てる
template<typename T>
struct SegmentTree{
  T identity;
  SegmentTree(T id):identity(id){}
  T merge(T x,T y){} // 書く

  const int MAX = 1<<17;
  T dat[MAX];

  // initとかqueryとか set_valとか
};
structにしてラムダ式を渡す
  • ライブラリの中身をいじる必要がない
  • （コピペなしで）複数本持てる
  • std::functionが遅い（は？）
template<typename T>
struct SegmentTree{
  using F = function<T(T, T)>;
  T identity;
  F merge;
  SegmentTree(F f, T id):merge(f), identity(id){}

  const int MAX = 1<<17;
  T dat[MAX];
  // initとかqueryとか set_valとか
};
ギャグ
  • decltypeを使うと、std::functionを使わずに済むので速い
template<typename T, typename F>
struct SegmentTree{
  T identity;
  F merge;
  SegmentTree(F f, T id):merge(f), identity(id){}

  const int MAX = 1<<17;
  T dat[MAX];
  // initとかqueryとか set_valとか
};

auto f=[&](int a,int b){return max(a,b);};
const int id = -1e9;
SegmentTree<int, decltype(f)> seg(f,id);
モノイドクラスを渡す
  • 疎結合になる
  • ローカル変数を参照できない
template<typename Monoid>
struct SegmentTree{
  Monoid identity = Monoid::identity;
  // マージには Monoid::merge を使う

  const int MAX = 1<<17;
  T dat[MAX];
  // initとかqueryとか set_valとか
};

struct Monoid{
  // メンバ変数を書く

  static Monoid identity; // 直す
  static Monoid merge(Monoid x,Monoid y){} // 書く
};

結局ラムダ式を渡すのとモノイドを渡すのはどっちがいいのか？

これはポジショントークなのでモノイド派の人も記事を書いてください。

RMQ with index の例

ラムダ式

using P = pair<int, int>;
auto f=[](P x,P y){return min(x,y);};
SegmentTree<int> seg(f,P(1e9,-1));

モノイド

struct Monoid{
  int val,idx;
  Monoid(int val,int idx):val(val),idx(idx){}
  static Monoid identity(1e9,-1);
  static Monoid merge(Monoid x,Monoid y){
    return x.val<y.val?x:y;
  }
};
SegmentTree<Monoid> seg;

ラムダ式の方がすっきりしてませんか？

AOJ 0367 ネットワークの課金システム の例

ネタバレになるんですが、マージ関数の中からmapを見たい場合があります。
モノイドを渡す方式だとmapをstatic変数にするかグローバルに置くかしないといけません
（僕が知らないだけかも　いい感じの書き方があったら教えてください）
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0367&lang=ja

ローカル変数のmapを見れる、そう、ラムダ式ならね。

結論

好みの問題なので両方書いてみてしっくりきた方を使えばいいのでは？
個人的にはラムダ式が楽だと思う。