Segment Tree (src/segtree.hpp)

Depends on

src/template.hpp

Required by

src/segtree2d.hpp

Verified with

Code

#pragma once
#include "template.hpp"

template<class S, S (*op)(S, S), S (*e)()> struct segtree {
    int n;
    vector<S> d;
    segtree(): segtree(1) {}
    explicit segtree(int n_): segtree(vector<S>(n_, e())) {}
    explicit segtree(const vector<S>& a): n(__bit_ceil(si(a))), d(n * 2, e()) {
        rep(i, si(a)) d[n + i] = a[i];
        for(int i = n; --i;) d[i] = op(d[i * 2], d[i * 2 + 1]);
    }
    void set(int i, S x) {
        for(d[i += n] = x; i >>= 1;) d[i] = op(d[i * 2], d[i * 2 + 1]);
    }
    S get(int i) { return d[i + n]; }
    S prod(int l, int r) {
        S L = e(), R = e();
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) L = op(L, d[l++]);
            if(r & 1) R = op(d[--r], R);
        }
        return op(L, R);
    }
    template<typename F> int max_right(int l, F f) const {
        if(l == n) return n;
        l += n;
        S sm = e();
        do {
            while(~l & 1) l >>= 1;
            if(!f(op(sm, d[l]))) {
                while(l < n) {
                    l <<= 1;
                    if(f(op(sm, d[l]))) sm = op(sm, d[l++]);
                }
                return l - n;
            }
            sm = op(sm, d[l++]);
        } while((l & -l) != l);
        return n;
    }
    template<typename F> int min_left(int r, F f) const {
        if(!r) return 0;
        r += n;
        S sm = e();
        do {
            r--;
            while(r > 1 and r & 1) r >>= 1;
            if(!f(op(d[r], sm))) {
                while(r < n) {
                    r = (2 * r + 1);
                    if(f(op(d[r], sm))) sm = op(d[r--], sm);
                }
                return r + 1 - n;
            }
            sm = op(d[r], sm);
        } while((r & -r) != r);
        return 0;
    }
};

template<class T> using SegtreeFrom = segtree<typename T::S, T::op, T::e>;

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 3 "src/segtree.hpp"

template<class S, S (*op)(S, S), S (*e)()> struct segtree {
    int n;
    vector<S> d;
    segtree(): segtree(1) {}
    explicit segtree(int n_): segtree(vector<S>(n_, e())) {}
    explicit segtree(const vector<S>& a): n(__bit_ceil(si(a))), d(n * 2, e()) {
        rep(i, si(a)) d[n + i] = a[i];
        for(int i = n; --i;) d[i] = op(d[i * 2], d[i * 2 + 1]);
    }
    void set(int i, S x) {
        for(d[i += n] = x; i >>= 1;) d[i] = op(d[i * 2], d[i * 2 + 1]);
    }
    S get(int i) { return d[i + n]; }
    S prod(int l, int r) {
        S L = e(), R = e();
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) L = op(L, d[l++]);
            if(r & 1) R = op(d[--r], R);
        }
        return op(L, R);
    }
    template<typename F> int max_right(int l, F f) const {
        if(l == n) return n;
        l += n;
        S sm = e();
        do {
            while(~l & 1) l >>= 1;
            if(!f(op(sm, d[l]))) {
                while(l < n) {
                    l <<= 1;
                    if(f(op(sm, d[l]))) sm = op(sm, d[l++]);
                }
                return l - n;
            }
            sm = op(sm, d[l++]);
        } while((l & -l) != l);
        return n;
    }
    template<typename F> int min_left(int r, F f) const {
        if(!r) return 0;
        r += n;
        S sm = e();
        do {
            r--;
            while(r > 1 and r & 1) r >>= 1;
            if(!f(op(d[r], sm))) {
                while(r < n) {
                    r = (2 * r + 1);
                    if(f(op(d[r], sm))) sm = op(d[r--], sm);
                }
                return r + 1 - n;
            }
            sm = op(d[r], sm);
        } while((r & -r) != r);
        return 0;
    }
};

template<class T> using SegtreeFrom = segtree<typename T::S, T::op, T::e>;