This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub shibh308/library
template<typename T> struct Segtree{ int n; T op; vector<T> elm; function<T(T, T)> f; Segtree(int n, T init, function<T(T, T)> f, T op = T()) : n(n), op(op), elm(2 * n, init), f(f) { for(int i = n - 1; i >= 1; --i) elm[i] = f(elm[2 * i], elm[2 * i + 1]); } Segtree(int n, vector<T> init, function<T(T, T)> f, T op = T()) : n(n), op(op), elm(2 * n), f(f) { for(int i = 0; i < n; ++i) elm[i + n] = init[i]; for(int i = n - 1; i >= 1; --i) elm[i] = f(elm[2 * i], elm[2 * i + 1]); } void set(int x, T val){ x += n; elm[x] = val; while(x >>= 1) elm[x] = f(elm[2 * x], elm[2 * x + 1]); } void update(int x, T val){ x += n; elm[x] = f(elm[x], val); while(x >>= 1) elm[x] = f(elm[2 * x], elm[2 * x + 1]); } T get(int x, int y) const{ T l = op, r = op; for(x += n, y += n - 1; x <= y; x >>= 1, y >>= 1){ if(x & 1) l = f(l, elm[x++]); if(!(y & 1)) r = f(elm[y--], r); } return f(l, r); } };
#line 1 "lib/classes/segtree.cpp" template<typename T> struct Segtree{ int n; T op; vector<T> elm; function<T(T, T)> f; Segtree(int n, T init, function<T(T, T)> f, T op = T()) : n(n), op(op), elm(2 * n, init), f(f) { for(int i = n - 1; i >= 1; --i) elm[i] = f(elm[2 * i], elm[2 * i + 1]); } Segtree(int n, vector<T> init, function<T(T, T)> f, T op = T()) : n(n), op(op), elm(2 * n), f(f) { for(int i = 0; i < n; ++i) elm[i + n] = init[i]; for(int i = n - 1; i >= 1; --i) elm[i] = f(elm[2 * i], elm[2 * i + 1]); } void set(int x, T val){ x += n; elm[x] = val; while(x >>= 1) elm[x] = f(elm[2 * x], elm[2 * x + 1]); } void update(int x, T val){ x += n; elm[x] = f(elm[x], val); while(x >>= 1) elm[x] = f(elm[2 * x], elm[2 * x + 1]); } T get(int x, int y) const{ T l = op, r = op; for(x += n, y += n - 1; x <= y; x >>= 1, y >>= 1){ if(x & 1) l = f(l, elm[x++]); if(!(y & 1)) r = f(elm[y--], r); } return f(l, r); } };