segtree1.cpp

template <class T>
class SegmentTree {
  const int n;
  vector<T> data;
  T sub(int l, int r, int node, int lb, int ub) const {
    if (ub <= l || r <= lb) return T();
    if (l <= lb && ub <= r) return data[node];
    T vl = sub(l, r, node * 2 + 0, lb, (lb + ub) / 2);
    T vr = sub(l, r, node * 2 + 1, (lb + ub) / 2, ub);
    return merge(vl, vr);
  }
public:
  SegmentTree(const int s) : n(1 << s), data(n * 2, T()) {}
  void update(int p, T val) {
    data[p += n] = val;
    while (p /= 2) {
      data[p] = merge(data[p * 2], data[p * 2 + 1]);
    }
  }
  T query(int l, int r) const {
    return sub(l, r, 1, 0, n);
  }
};