Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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);
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement