C++: セグメント木の実装
template <typename T, typename Compare=std::less<T> > class SegmentTree { public: SegmentTree(int num, T default_value=T()) : default_(default_value) { num_ = 1; while (num_ <= num) num_ <<= 1; dat_.resize(2 * num_ - 1, default_); } void Update(int index, T value) { index += num_ - 1; dat_[index] = value; while (index > 0) { index = (index - 1) / 2; dat_[index] = Compare_(dat_[index * 2 + 1], dat_[index * 2 + 2]); } } // [from, to] T Query(int from, int to) { return Query_(from, to + 1, 0, 0, num_); } private: std::vector<T> dat_; int num_; T default_; T Compare_(T x, T y) { return Compare()(x, y) ? x : y; } T Query_(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return default_; if (a <= l && r <= b) { return dat_[k]; } else { T vl = Query_(a, b, k * 2 + 1, l, (l + r) / 2); T vr = Query_(a, b, k * 2 + 2, (l + r) / 2, r); return Compare_(vl, vr); } } };
0 件のコメント:
コメントを投稿