Segment tree in C++

C++: セグメント木の実装

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

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);     }   } };