セグ木テンプレ
C++11用オレオレセグ木テンプレです。
「変更するコードここから」の下を書き換えて使います。
segment_tree<int, 1000> seg;
で要素int,大きさ1000のセグ木が出来ます。2の累乗には勝手に拡張するので1024でなくて良いです。
これをそのまま使うのではなく、これは一例と思っておいて自分用にカスタマイズするのが良いかと思います。
#include <cstdint> inline constexpr uint32_t get_min2pow(uint32_t value, uint32_t work = 1) { return ((value <= work) ? (work) : (get_min2pow(value, work * 2))); } template<typename value_type_, uint32_t N_RAW_MAX> class segment_tree { public: using value_type = value_type_; static constexpr uint32_t N_MAX = get_min2pow(N_RAW_MAX); private: value_type default_value; value_type value[N_MAX * 2 - 1] = {}; static inline constexpr int32_t getchild(int i) { return i * 2 + 1; } static inline constexpr int32_t getparent(int i) { return (i - 1) / 2; } void Init_impl(int k = 0) { if (k < N_MAX - 1) { //ノード auto c1 = getchild(k), c2 = c1 + 1; Init_impl(c1); Init_impl(c2); value[k] = merge(value[c1], value[c2]); } else { //葉 value[k] = default_value; } } value_type query_impl(int32_t a, int32_t b, int32_t k = 0, int32_t l = 0, int32_t r = N_MAX)const { if (r <= a || b <= l)return default_value; if (a <= l && r <= b)return value[k]; int m = (l + r) / 2; return merge(query_impl(a, b, getchild(k), l, m), query_impl(a, b, getchild(k) + 1, m, r)); } public: template<typename T, typename FUNC> void change(int32_t i, T&& v, FUNC&& operation = std::plus<>{}) { i += N_MAX - 1; //葉 value[i] = std::forward<FUNC>(operation)(std::move(value[i]), std::forward<T>(v)); i = getparent(i); //ノード for (;;) { auto c1 = getchild(i), c2 = c1 + 1; value[i] = merge(value[c1], value[c2]); if (i == 0) { break; } i = getparent(i); } } //-----------------------------変更するコードここから-----------------------------// private: static inline value_type merge(const value_type& l, const value_type& r) { ここを書く; //RMQ return std::min(l, r); //RSQ return l + r; } public: inline void init() { default_value = 例外値を書く; //全ての葉にdefault_valueを設定し、親はマージで算出(非効率だけど計算量(N)だし気にしない) Init_impl(); } inline value_type query(int32_t a, int32_t b)const { //デフォルト実装は区間をマージするだけ(たぶんいじることは少ない) return query_impl(a, b); } };
使い方追記
segment_tree<int, 1000> seg; seg.init();//必要です seg.change(5,10);//5番目の要素に10加算します seg.change(10,10,[](auto,auto v){return v;});//10番目の要素を10にします seg.query(0,10);//[0,10)にクエリをします