ACL segtree 忘備録 - pandersonの日記

AtCoder Library 最近ようやく確認しました。
modintとか自分で実装しようとすると時間かかるやつがすぐ使えて（自分より）バグがなく使えるのほんとありがたい。
けど、素人には公式の使い方資料わかりづらい。ということで、忘備録。（あとで公式資料リンク張る）
まずは "segtree"　
セグメント木ってやつですね。

使った例
atcoder.jp
　

宣言のまえに

セグメント木の宣言のために、木の定義に使う二項演算 opと単位元 eを宣言しておく必要がある。
細かいことは省くとして、ざっと以下のような感じ。
・二項演算：木の要素をどのように上るかのルールみたいなもの
・単位元：「任意の木の要素 a 」vs 「単位元 e」で二項演算したときに、必ず a が返るような元。掛け算の１みたいな。
　
で、例えば「区間の最大値を要素に持つようなsegtree（要素はすべて正のint）」を考える場合は、こんな感じに先に定義しておく。

int op(int a, int b){ return max(a,b);}
int e(){return -1;}

以下、この op, e の segtree で説明する。
　
　

宣言

2通りあるらしい。

#include <atcoder/all>
using namespace atcoder;

int N=4; //segtreeのサイズ
vector<int> v = {1,2,3,4}; //初期値にしたいベクトル

segtree<int, op, e> seg(N); //サイズNのsegtreeを宣言
segtree<int, op, e> seg(v); //初期値をv、サイズをv.size()とするsegtreeを宣言

値の代入、取得

seg.set(i, 10); //seg[i] = 10 代入
seg.get(0); // seg[0]を取得

ある区間における目的の要素を取得

日本語難しい。
今のopの例だと、「ある区間における最大の要素を取得」することが高速にできる。
これが便利。

seg.prod(1,4); // 1≦i<4 における最大のseg[i]を取得。半開区間であることに注意
seg.all_prod(); // =seg.prod(0,N) 全区間に対して実行する場合はこれが使える

なんか条件を満たす区間の右端を探す的な

日本語難しい。
以下のようにすると、「i=l から右に見て行って、seg[i] < V を満たし続ける（seg[l] < V && seg[l+1] < V && …）区間の右端のインデックス r 」を得ることができる。

int V=3;
bool f(int a){ return a<V ;} // 先に条件fを定義しておく
seg.max_right<f>(l);

上記のように、2段階で実行する。
なお、返ってくるrは半開区間のときのrであることに注意。
つまり [l,r)においてseg[i] < V だが、seg[r] ≧ V となっている。

とりあえずこんな感じでしょうか