template <class T>
class SegmentTree {
  const int n;
  vector<T> data;
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 {
    l += n; r += n;
    T res1 = T(), res2 = T();
    while (l != r) {
      if (l % 2) res1 = merge(res1, data[l++]);
      if (r % 2) res2 = merge(data[--r], res2);
      l /= 2; r /= 2;
    }
    return merge(res1, res2);
  }
};