セグメント木を追加

koba-e964 commented 6 years ago

設計について、

データ型とそれの上の演算を別に渡す
データ型に演算を含めるの2種類の方法が考えられますが、後者 (データ型に演算を含める) を採用します。理由は以下の3点です。
データ型と別に演算を渡す形式だと、演算の型をテンプレート引数に含める必要があり、書くのに手間がある
- 参考: https://github.com/comp-prog-jp-library-standard/competitive-programming-library/blob/66e4f10321d3636c194f28cab25d9539aa81a9e4/library/cpp/src/array/segment_tree.cpp#L3
- セグメント木であればまだ少ないが、遅延セグメント木などになると多くなる
型推論を働かせるためにヘルパー関数なども必要になる
- こういうの https://github.com/comp-prog-jp-library-standard/competitive-programming-library/blob/ac854c5d8c796507cbb034ccc38b94414e9cf6c0/library/cpp/src/array/segment_tree.cpp#L65-L69
定義が1箇所にまとまっている方がわかりやすい

asi1024 commented 6 years ago

O(1) の operator[] もあったほうが嬉しそう

asi1024 commented 6 years ago

size_type, value_type メンバ型

koba-e964 commented 6 years ago

これって segTree[i] = val; みたいにできた方が嬉しいでしょうか?

asi1024 commented 6 years ago

それはできなくても良さそう．できてもよいが．(updateを遅延させるなりして)

asi1024 commented 6 years ago

列からの O(n) 初期化とかあってもいいですね (std::vector を受けるか，あるいは begin, end を受けるか)

asi1024 commented 6 years ago

ベンチマークは， #31 らへんが解決した後でもよいと思います．

asi1024 commented 6 years ago

make_range_min_query<T>(size) みたいなのも欲しい

asi1024 commented 6 years ago

コメント箇所以外はLGTMです

koba-e964 commented 6 years ago

修正しました

comp-prog-jp-library-standard / competitive-programming-library