Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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);
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment