Create a gist now

Instantly share code, notes, and snippets.

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