segment_tree.cpp

template<typename T, const T& Combine(const T&, const T&)>
class segment_tree {
    darray<T> v;
    T default_value;
    T combine_considering_default(const T& left_value, const T& right_value) const {
        if (left_value == default_value) {
            return right_value;
        } else if (right_value == default_value) {
            return left_value;
        } else {
            return Combine(left_value, right_value);
        }
    }
public:
    explicit segment_tree(usize size) : default_value(T()) {
        v.reserve(size << 1u);
        for (usize i = 0u; i < size; i++) v.push_back(default_value);
        for (usize i = 0u; i < size; i++) v.push_back(default_value);
    }
    segment_tree(usize size, T default_value) : default_value(default_value) {
        v.reserve(size << 1u);
        for (usize i = 0u; i < size; i++) v.push_back(default_value);
        for (usize i = 0u; i < size; i++) v.push_back(default_value);
    }
    explicit segment_tree(const darray<T>& values_src) : default_value(T()) {
        v.reserve(values_src.size() << 1u);
        for (usize i = 0u; i < values_src.size(); i++) v.push_back(default_value);
        for (usize i = 0u; i < values_src.size(); i++) v.push_back(values_src[i]);
        update_all();
    }
    segment_tree(const darray<T>& values_src, T default_value) : default_value(default_value) {
        v.reserve(values_src.size() << 1u);
        for (usize i = 0u; i < values_src.size(); i++) v.push_back(default_value);
        for (usize i = 0u; i < values_src.size(); i++) v.push_back(values_src[i]);
        update_all();
    }
    segment_tree(const segment_tree& src) : v(src.v), default_value(src.default_value) {}
    segment_tree(segment_tree&& src) noexcept : v(move(src.v)), default_value(move(src.default_value)) {}
    segment_tree& operator=(const segment_tree& src) { self = segment_tree(src); return self; }
    segment_tree& operator=(segment_tree&& src) noexcept { v = move(src.v); default_value = move(src.default_value); return self; }
    void modify_without_update(usize i, const T& value) {
        v[(v.size() >> 1u) + i] = value;
    }
    void modify(usize i, const T& value) {
        modify_without_update(i, move(value));
        for (usize v_index = ((v.size() >> 1u) + i >> 1u); v_index > 0u; v_index >>= 1u) {
            update(v_index);
        }
    }
    void update(usize v_index) {
        if (v_index == 0u || v_index >= (v.size() >> 1u)) return;
        v[v_index] = combine_considering_default(v[(v_index << 1u)], v[(v_index << 1u) | 1u]);
    }
    void update_all() {
        for (usize v_index = (v.size() >> 1u) - 1u; v_index > 0u; v_index--) update(v_index);
    }
    T query(usize begin, usize end) const {
        T result_left = default_value;
        T result_right = default_value;
        for (usize left = begin + (v.size() >> 1u), right = end + (v.size() >> 1u); left < right; left >>= 1u, right >>= 1u) {
            if (left & 1u) {
                result_left = combine_considering_default(result_left, v[left]);
                left++;
            }
            if (right & 1u) {
                result_right = combine_considering_default(v[right - 1u], result_right);
                right--;
            }
        }
        return combine_considering_default(result_left, result_right);
    }
};

갓