10.29.2011

Segment tree in C++

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 件のコメント:

コメントを投稿